Mergesort

An mergesort breaks a list of elements down into single elements by continually halving it. Once the list is down to single elements, those elements are then merged together by using a sorting method, until the list is together again, but in sorted order. The speed of a mergsort is O(n log(n)), which is significantly faster than an insertion sort, which is O(n^2).

Type a word into the box below and press sort to see the letters sorted alphabetically by a merge sort.

Word:

Description

For a merge sort there are two important elements that have to be understood.

1. Sorting two ordered lists is faster than sorting an unordered list. To sort an unordered list with a straight insertion sort takes O(n^2) for n list items. For two ordered list it only takes one pass through the list, or O(n).
2. You can break a list down binarily to single elements by continually halving it. The number of times you half the list is O(log(n)).

Let's look at each in turn.

First, sorting two ordered lists into one ordered list requires only one pass, n, through the list, whereas sorting an unordered list can require n^2 passes.

For example, these two sorted lists "aceg" and "bdfh" requires only one pass if we want to combine them into one sorted list. The method is to compare the left most character in each list, remove the smallest one and place it in the new combined list until all characters are removed from both lists.

So, 'a' is compared to 'b' and 'a' is removed and added to the new list, leaving the two lists "ceg" and "bdfh". Then, 'c' is compared to 'b' and 'b' is removed and added to the new list, leaving "ceg" and "dfh". Then, c is compared to 'f' and 'c' is removed and added to the new list, leaving "eg" and "dfg", etc., until you end up with "abcdefgh".

Second, you can break a list up by continually splitting it into two parts down to single elements. It takes log(n) splits to break down a string of length n. With very few steps you can break up very large strings this way. And, you can also go in the reverse direction and combine lists very quickly to get back to a whole list again. The mergesort goes in both direction, first splitting a list up into single elements and then combining, while sorting them and reconstituting an ordered list.

Building on 1 and 2 above, you can combine values two at a time from an unsorted list and at each stage end up with sorted lists to combine. Sorted lists mean you only have to make one pass through them to create another ordered list from them.

For example, If I have the letters "hgfedcba", I can merge sort them thus:

I split them up into single letters by dividing by two until I get to this:

h g f e d c b a

and then I combine them two at a time, and compared and sort them, to get the next stage:

gh ef cd ab

Now I have four sorted lists. If I then combine these two at a time and sort them I get:

efgh abcd

Now I have two sorted lists! So, one more pass through these lists and I get

abcdefgh.

So, with three passes through the list at three levels I have a sorted list! That's a total
of n*log(n)

That's the essence of the merge sort. Now for some details.

The mergesort is a divide-and-conquer method of sorting. I think a better name for it would have been split-merge sort, because you first split a list up into single elements, and then you merge while sorting the single elements.

Below is another example with a diagram to help clarify the idea better.

Diagram 1

Diagram 1 above shows how a mergesort works. The unsorted string "FDGEAHBC" is first split up into single characters by successive halving of the word, then the string is reformed by successive merging and sorting of the sub strings.

In diagram 1, the string is broken into 8 single elements and then it is reformulate at levels 1, 2 and 3 (numbers are on the diagram). At each level there are a total of 8 characters, so this means there is one pass through 8 characters at each level, and there are also log(8), or 3, levels.

The Algorithm

Below is the mergesort pseudocode. Since the mergsort lends itself to using recursion, the "mergesort()" function is called by itself in order to split the item string passed in "s[]" down to single elements. The "merge()" function combines two buffers back into the original string, but in sorted order. Note that the mergesort algorithm uses recursion, where the function calls itself over and over again.