The Merge Sort uses the divide-and-conquer approach. It begins by placing each element into its own individual list. Then each pair of adjacent lists is combined into one sorted list. This continues until there is one big, final, sorted list. The process is illustrated below:
The above, however, is a very simplistic approach. In reality, the merge sort is often implemented recursively.
A Merge Sort method:
How it works:
The recursive calls to sort and the resulting recalculation of middle = (left + right) / 2 continually subdivide the lists until we get individual “lists” of one element each. Due to the nature of recursion, that subdivision process continues until we reach the final lists of one element each before themerge method actually begins merging the lists together, two at a time.
Subdividing the list:
On the following page we see this process of recursively subdividing and subsequent merging of the lists. We will consider the following original order of some numbers to be sorted:
|
7 |
8 |
6 |
2 |
3 |
5 |
Notice above that the all splitting processes occur first until after Step 4 at which time all “lists” consist of single elements. At that point successive merging of all the lists takes place according to how the split steps were originally done, but in reverse order.
Salient features #2 and #3 pointed out in the code on the previous page are the result of recursion. This corresponds to Steps 2-4 above in which a hierarchy of unordered lists are produced as a result of splitting previous lists. Steps 5-7 implement salient feature #4 which is the reverse order merging of those lists.