How to use Merge Sort the sorting algorithm with Example?

MERGE SORT

Merge Sort is somewhat difficult to comprehend (it’s not impossible J ) but the gain is the high effeciency of the sorting algorithm. The merge sort is achieved by splitting an array into two, then sorting each of the subarrays and finallry merging them. Merging is a process of comnining two separately sorted files into a single sorted file. Basically in merge sort, sorting of an array is being achieved by sorting two subarrays of smaller lengths. Thus the merge sort can best be viewed as a recursive procedure. What is the breaking condition then? An array having one element is always sorted.
Let us consider a case, that we have to sort an array whose lower bound is lower and upper bound is upper. Now an algorithm to sort this array using merge sort will be:
       If( lower = = upper)
                                 array is already sorted
      else {

                                                                                i.            claculate middle index of the array [middle = (lower+ upper)/2 ]

                                                                              ii.            merge sort the subarray from lower to middle

                                                                            iii.            merge sort the subarray from middle+1 to upper

                                                                            iv.            merge the two sorted subarrays into a single sorted array

}

Now let us consider an example to illustrate the algorithm. We are given an array of four elements: 62, 12, 5, 57 so the lower=0 and upper=3

(62 12) (5 57)
(62)(12)(5 57)
(12 62) (5 57)
(12 62)(5)(57)
(12 62) (5 57)
(5 12 57 62)

Now a little explanation about the above figure follows. In step1 middle is calculated and two subarrays (62, 12) and (5, 57) are formed First subarray is to be sorted now. In step 2 middle is calculated for the subarray(62,12) and now we get two subarrays of one element each. As single element array is already sorted, we now merge the two subarrays (62) and (12) in step 3, resulting in a single array (12,62). Now sort is called for the initially obtained second subarray (5, 57). As a result in step 4, it is splitted into two subarrays (5) and (57) of one element each, which are already sorted. They are merged to yield a single array (5, 57) in step 5. Now in step 6, we have two sorted subarrays (12, 62) and (5, 57) which are merged to obtain a single sorted array (5, 57, 12, 62). Voila!!!