# DIVIDE AND CONQUER MERGE SORT

Divide and Conquer is an algorithmic pattern. In algorithmic methods, the design is to take a dispute on a huge input, break the input into minor pieces, decide the problem on each of the small pieces, and then merge the piecewise solutions into a global solution. This mechanism

of solving the problem is called the Divide & Conquer Strategy.

Divide and Conquer algorithm consists of a dispute using the following three steps.

❖ Divide the original problem into a set of sub problems recursively.

❖ Conquer: Solve every sub problem individually.

❖ Combine: Put together the solutions of the sub problems to get the solution to the whole problem.

Merge sort is a **stable sort.**

Merge sort is** not **a **in place sort** therefore, the memory size of the input must be allocated for the sorted output to be stored in n/2 extra spaces.

#### COMPLEXITY:

Since each recursive step is one half the length of n . Since we know that merge sort is O(n log n) could stop here as Merge Sort is called log n times, the merge must be called n times. But we can also reason that we must subdivide the n items until each input consists of one element.

**Fundamental of Divide & Conquer Strategy**

❖ Relational Formula: It is the formula that we generate from the given technique.

After generation of Formula we apply D&C Strategy, i.e. we break the problem recursively & solve the broken sub problems.

❖ Stopping Condition: When we break the problem using Divide & Conquer Strategy, then we need to know that for how much time, we need to apply divide & Conquer.

So the condition where the need to stop our recursion steps of D&C is called as Stopping Condition.

#### Advantages of Divide and Conquer Algorithms

❖ The first, and probably the most recognizable benefit of the divide and conquer paradigm is the fact that it allows us to solve difficult, sometimes even NP problems.

❖ Being given a difficult problem can often be discouraging if there is no idea how to go about solving it. However, with the divide and conquer method, it reduces the degree of difficulty since it divides the problem into easily solvable subproblems.

❖ Another advantage of this paradigm is that it often plays a part in finding other efficient algorithms. In fact, it played a central role in finding the quick sort and merge sort algorithms.

❖ It also uses memory caches effectively. The reason for this is the fact that when the subproblems become simple enough, they can be solved within a cache, without having to access the slower main memory, which saves time and makes the algorithm more efficient.

❖ And in some cases, it can even produce more precise outcomes in computations with rounded arithmetic than iterative methods would.

❖ In the divide and conquer strategy we divide problems into subproblems that can be executed independently from each other. Thus, making this strategy suited for parallel execution.

**Disadvantages of Divide and Conquer Algorithms**

One of the most common issues with this sort of algorithm is the fact that the recursion is slow, which in some cases outweighs any advantages of this divide and conquer process.

Another concern with it is the fact that sometimes it can become more complicated than a basic iterative approach, especially in cases with a large n.

In other words, if someone wanted to add large numbers together, if they just create a simple loop to add them together, it would turn out to be a much simpler approach than it would be to divide the numbers up into two groups, add these groups recursively, and then add the

sums of the two groups together.

## Recursion

It will be easier for those who have seen the movie Inception. Leonardo had a dream, in that dream he had another dream, in that dream he had yet another dream, and that goes on. So it’s like there is a function called dream(), and we are just calling it in itself.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
function dream() { print "Dreaming" dream() } ---- void recursion() { recursion(); } int main() { recursion(); } ---- int fact(int n){ if(n == 0){ return 1; } return (n * fact(n-1)); } ---- |

## Algorithm:

Step 1 − if it is only one element in the list it is already sorted, return.

Step 2 − divide the list recursively into two halves until it can no more be divided.

Step 3 − merge the smaller lists into new list in sorted order.

### Procedure:

DAC(ARR, LB, UB) // T(n)

{

if(small(ARR, LB, UB))

return(Solution(ARR, LB, UB))

else

mid = (LB + UB) / 2 // f(1)

SP1 = DAC(ARR, LB, mid) // T(n/2)

SP2 = DAC(ARR, mid+1, UB) // T(n/2)

S = combine(SP1, SP2)

return(S)

}

Pseudocode:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
procedure mergesort( var a as array ) if ( n == 1 ) return a var l1 as array = a[0] ... a[n/2] var l2 as array = a[n/2+1] ... a[n] l1 = mergesort( l1 ) l2 = mergesort( l2 ) return merge( l1, l2 ) end procedure procedure merge( var a as array, var b as array ) var c as array while ( a and b have elements ) if ( a[0] > b[0] ) add b[0] to the end of c remove b[0] from b else add a[0] to the end of c remove a[0] from a end if end while while ( a has elements ) add a[0] to the end of c remove a[0] from a end while while ( b has elements ) add b[0] to the end of c remove b[0] from b end while return c end procedure |

## Python Program:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
def mergeSort(arr, l, r): if l<r: m= (l+(r-1))//2 # Finding the mid of the array mergeSort(arr,l,m) mergeSort(arr,m+1, r) mergex(arr,l,m,r) def mergex(arr, l, m, r): n1=m-l+1 n2=r-m #create temp array L=[0]*(n1) R=[0]*(n2) #Copy data to temp arrays L[] and R[] for i in range(0,n1): L[i]=arr[l+i] for j in range(0,n2): R[j]=arr[m+1+j] #Merge the temp arrays back i=0; j=0; k=l; while i<n1 and j < n2: if L[i]<=R[j]: arr[k]=L[i] i+=1 else: arr[k]=R[j] j+=1 k+=1 #copy the remaining elements while i<n1: arr[k]=L[i] i+=1 k+=1 #copy the remaining elements while j<n2: arr[k]=R[j] j+=1 k+=1 def printList(arr): #Code to print the list for i in range(len(arr)): print(arr[i],end=" ") print() arr=[21,11,5,78,49,54,72,88,56,28,10] print("List before sorting: ", end="\n") n=len(arr) printList(arr) mergeSort(arr,0,n-1) print("List after sorting: ",end="\n") #printList(arr) for i in range(n): print("%d "%arr[i],end=" ") |

## C Program:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
#include<stdio.h> #define max 10 int a[11]={21,11,5,78,49,54,72,88,56,28,10}; int b[10]; void merging(int low, int mid, int high) { int l1, l2, i; for(l1=low, l2=mid+1, i=low; l1<=mid && l2<=high; i++) { if(a[l1] < a[l2]) b[i]=a[l1++]; else b[i]=a[l2++]; } while(l1<=mid) { b[i++]=a[l1++]; } while(l2<=high) { b[i++]=a[l2++]; } for(i=low; i<=high; i++) { a[i]=b[i]; } } void sort(int low, int high){ int mid; if(low<high) { mid=(low+(high-1))/2; sort(low,mid); sort(mid+1,high); merging(low,mid,high); } else{ return; } } int main(){ int i; printf("\nList before sorting: "); for(i=0; i<=max; i++) { printf("%d ",a[i]); } sort(0,max); printf("\nList after sorting: "); for(i=0; i<=max; i++) { printf("%d ",a[i]); } } |

#### Input Output

1 2 3 4 |
List before sorting: 21 11 5 78 49 54 72 88 56 28 10 List after sorting: 5 10 11 21 28 49 54 56 72 78 88 |

**Divide & Conquer Strategy used in**

❑ Binary Search

❑ Tower of Hanoi

❑ Merge Sort

❑ Quick Sort

❑ Heap Sort

❑ Strassen’s Algorithm

Merge Sort, which sorts an array in O(n Log n) Time. This sort is not a in place sort but it is a stable sort. Merge Sort dividing technique is it divides the hole array into two parts and go through left part first, after that again divides (if possible) that sub array into two parts, and go for left part, (recursively doing it un till one element is left) then go to last division and goes for right part, and after that, merge function call to join both left 1 element and right one element, after that, it execute last previous step and going for right side to divide and then merge and then come back for upper layer division. As mentioned in the above diagram.