Merge Sort

Consider the first two elements (0 and 1) as being lists of length 1 (and therefore sorted) and merge them. Then do the same on elements 2 and 3. Now merge the two 2-lists you have, and repeat. Time-complexity is O(n log n). Stable. Requires extra space, about half the size of the actual dataset. On typical numeric data, uses fewer comparisons than QuickSort but has enough more overhead that it ends up being slower; a good algorithm, then, when comparison is slow for some reason. There are sophisticated variants of mergesort that do better at taking advantage of patterns in the input data; see http://mail.python.org/pipermail/python-dev/2002-July/026897.html for a description of one. (This is probably the best algorithm if you have to sort a LinkedList; try to write it in LispLanguage to fully appreciate it)

If your data is much larger than RAM, and you have (at least) 3 disks or tapes you can shuffle the data between, MergeSort is the fastest possible sort (see TheArtOfComputerProgramming for details - including a fold out with data layout on the discs; compare AlgorithmsDealingWithMassiveData).

MergeSort can also be implemented non-recursively; attempting to write a non-recursive QuickSort, as best I can tell, ends up producing something that looks very suspiciously like the non-recursive MergeSort.

Possibly interesting moderately recent papers:

Proximity Mergesort: optimal in-place sorting in the cache-oblivious model (available in pdf format from ACM if you have a [free] ACM Web account - click http://www.acm.org/account/create.html to create one).

Did you confirm that the article definitely is available via such a free account, or does it just look at first glance like it might be? I was under the impression, from experimenting a few months ago, that such things always required the $168 per year fee ($84 membership plus $84 service fee). Yes, confirmed it is free. Initially, I had difficulty saving the document locally, but I succeeded eventually.

Practical in-place mergesort - http://www-ihm.lri.fr/~thomas/VisuTri/inplacestablesort.html

Dubious claims about a inplace MergeSort (See SchwarzMergeSortAlgorithm?) moved to MergeSortDiscussion.

I don't understand the logic behind all of the above comments talking about QuickSort and MergeSort suddenly becoming similar if non-recursive versions are done. That seems to miss the whole point.

They are similar to start with; both use DivideAndConquer to split input lists into two sub-lists, and each sub-list is (conceptually) recursed upon.

The difference between the two is how they treat the sub-lists and their relationships with the whole. MergeSort (simplest form) splits a list into two-roughly-equal-sized sub-lists and merges them; recursively (in concept), this guarantees a final complete order. QuickSort splits a list into two sub-lists based on comparison of sub-list values with a pivot element chosen (simplest form) randomly.

There are lots of variations on the theme for both algorithms, but skipping that, I really do not see why anyone would claim that QuickSort starts to look like MergeSort if one implements the recursion by hand. It does not. MergeSort does not use pivots, period.

As a side note, QuickSort is not inherently a ternary DivideAndConquer, but it's perhaps the most common approach, whereas MergeSort is clearly most commonly a binary DivideAndConquer (it would be interesting to see a pointer to a ternary version; none come to mind), so that should probably be addressed as well. -- DougMerritt

See SortingAlgorithms

CategoryAlgorithm