Merge Sort(Algorithm)

The merge sort is another sorting technique that uses the divide and conquer approach.i.e. it breaks the original problem into sub-problems similar to the original problem but smaller in size;then it solves each subproblem recursively ;and then combines all the solved sub-problems.Hence the merge sort follows the following procedure:
Divide-divide the n-element array into sub-sequence of n/2 elements each.
Conquer-Sort the two sub-sequence recursively.
Combine-Merge the two sorted sub-sequences.
When the array is of length 1,it is already sorted.The main step is the combine step.So first we will deal with it.
For merging we call a method Merge(A,p,q,r) ,where A is the array ,p,q,r are the indices of array such that p<=q<r.Here we assume that the sub-arrays A[p..q] and A[q+1..r] are already sorted.You can imagine it as a couple of piles of sorted cards (smallest on top).We wish to merge both of them.So we take up the topmost card from each pile ,find the smaller out of them and place it to the third pile(the output pile).Like this we keep on comparing the topmost cards from each pile,and place the smaller in the output pile until one of the piles is empty , after which we can simply place the other pile in the output pile.We can check this condition(of the pile being empty) by placing am imaginary card of value infinte(called the sentinel card) at the end of both the piles.We use infinity because on reaching it on one of the piles,the other pile will only have cards smaller than it(except the sentinel card of that pile).Here is the pseudocode of the merge procedure

Merge(A,p,q,r)
n1=q-p+1   //n1 is the size of the first pile
n2=r-q        //n2 is the size of the second pile
create arrays Left[1....n1+1] and Right[1.....n2+1]
for i=1 to n1
      L[i]=A[p+i-1]
for j=1 to n2
      R[j]=A[q+j]
L[n1+1]=infinity
R[n2+1]=infinity
i=j=1
for k=p to r
    if L[i]<=R[j]
         A[k]=L[i]
         i=i+1
    else
         A[k]=R[j]
         j=j+1

Merge Sort

 Now that we have seen how the merge procedure works,it is simple to divide the array and sort each sub-division.the method merge-sort(A,p,r) takes the initial array A from indices p to r and recursively divides it and sends the sub -arrays to the merge procedure.It should be noted that if p>=r then the array has at most 1 element which is already sorted.Hence the procedure lokks like this:

Merge_Sort(A,p,r)
if p<r
      q=(p+r)/2    //division into two sub-arrays
       Merge_Sort(A,p,q)
       Merge_Sort(A,q+1,r)
       Merge(A,p,q,r)

To sort the entire array the initial call should be Merge_Sort(A,1,A.length)
The time complexity of the merge sort in worst case is Theta(n lg(n)).You can know more about time complexities in the Time Complexities page.