Merge - sort The divide and conquer way

Merge sort is one of the qucik sorting alogorithms that uses the Divide and conquer strategy and programmatically recursion

This is how it goes

The array that has to be sorted is divided into 2 halfs.each of these 2 halfs are sorted independently.Now these 2 halfs are merged to give the full sorted array.As one can easily claim the two independent halfs are again sorted using the same mergesort algorithm wherein they are divided into 2 more halfs and so on.....the recursion ends when the divided half contains only one element....
Now the most important part is to merge the 2 sorted halfs into a sorted array of elements.

This is the pseudo code for the recursive mersort function

void mergesort(int low, int hi)
{
   if (low < hi)
   {
       int middle=(low+hi)/2;
       mergesort(low, m);
       mergesort(middle+1, hi);
       merge(lo, middle, hi);
   }
}

We find the middle elemsnt and divide the array into 2 halfs.Then recursively aply the same algorithm for the 2 halfs.
As stated above the recursion stops when low = hi or there is only one element in the array i.e low and hi coincide to be same.

Now the more important part is the merge function.Lets see how it goes
The efficient way of implementing this goes here

We have to use an other auxiliary array B which is atleast as big as the first half

Now copy the elements of the first half of the array a to b.Now compare the elements of first half in b and the second half in a one by one
Whichever is smaller is copied on to the next position in a.End the loop when we reach the end of either of the half

Analysis:
As we can see we have to implement the function merge log(n) times.
Now the function merge requires at the max copying it to the auxiliary array once and copy it back to the original array,Thus 2n times
Thus the total time complexity is 2nlog(n) i.e of the order nlog(n).This is very  scalable
That is why mergesort is one of the earlier winners in the sorting contest

Thanks,
Prasanna


}