MERGE SORT

• Divide: Partition the n_element sequence to be sorted into 2 sub-sequence of n/2 elements each.
• Conquer: Sort the two sub-sequence recursively using the merge sort.
• Combine:Merge the two sorted sub-sequence of size n/2 each to produce the sorted  sequence consisting of n elements.

          Procedure merge-sort(first,last,array)
                 Mid=(first,last)/2;
                 Merge-sort(first,mid,array)
                 Merge-sort(Mid+1,last,array)
                 Rejoin-two-halves(Mid,array)
         End Merge-sort. 

EXAMPLE 

To understand merge sort, we take an unsorted array as the following,

               

We  know that merge sort first divides the whole array iteratively into equal halves .

         

Now we divides these array into two halves.

       

We further divide these arrays and we achieve atomic value which can no more be divided.

Now,we combine them in exactly the same manner as they were broken down.we first compare the element for each list and then combine them into another list in a sorted manner.

In the next iteration of the combining phase,we compare lists of two data values,and merge them into a list of found data values placing all in a sorted order.

After the final merging the list should look like this,

Advantages:

• It is fast and stable sorting method.
• It is always ensure an efficiency of  O(nlogn)

Disadvantages:

• It requires additional memory space to perform sorting .the size of the additional space is in direct proportion to the size of the input list.
• Even though the number of comparisons made by merge sort are nearly optimal,its performance is slightly lesser than that of quick sort.

                                      *****