Merge Sort and Quicksort

The two sorts that reach n log n make the same move: split the problem, sort the pieces, combine them. They differ in where they spend the effort. Merge sort splits blindly and works hard to combine; quicksort works hard to split and combines for free.

That one choice decides everything else about them: how much memory each needs, whether equal items keep their order, how kindly each treats the cache, and the one kind of input that turns quicksort quadratic. Almost every library sort in use today is built from one of the two.

Merge Sort: Split, Then Merge

Halve the array, halve the halves, and keep going until every piece holds one item, which is sorted by definition. Then merge pairs of pieces back together by repeatedly taking the smaller of the two front items. Two sorted runs of four become one sorted run of eight in at most seven comparisons.

Every level of merging touches every item once, about n work per level, and halving a million items down to single items takes 20 levels. So merge sort costs about n log n, 20 million steps for a million items, on any input: sorted, reversed or random. Counted on a million random numbers, a plain merge sort made 18.7 million comparisons.

What Merging Costs

Merging two runs needs somewhere to put the result, a buffer beside the data. The textbook version needs a buffer as large as the whole array; Timsort, CPython's merge-based sort, needs at most half of it. So sorting 1 GB in memory can need another half to full gigabyte at the peak of the sort.

In exchange, merge sort reads and writes strictly in sequence: each merge streams through two runs from front to back and writes one output from front to back. That makes it the natural sort for linked lists, which cannot jump to a middle element anyway, for disks, where sequential reads are the cheap ones, and for data bigger than memory, which Sorting in the Real World takes up.

Quicksort: Partition, Then Recurse

Pick one item as the pivot. Move everything smaller than the pivot to its left and everything larger to its right, in place, by walking two indexes toward each other and swapping pairs that sit on the wrong side. Then sort each side the same way.

There is nothing to combine: once both sides are sorted, the whole array is. The extra memory is only the recursion, about log n levels of it. And the partition pass is a sequential scan from both ends, which the cache rewards (Chapter 4). That is why a well-pivoted quicksort usually beats merge sort on arrays in RAM.

The inner loop is also as small as a loop can be. Every item in the pass is compared with the same pivot, which in compiled code stays in a register for the whole pass, and most items move nowhere, because they are already on the correct side. Merge sort, by contrast, writes every item to the buffer at every level, so it moves about n log n items in total even when the input was nearly sorted. Counting comparisons, merge sort makes somewhat fewer; counting memory traffic, quicksort usually does less.

The Worst Case and the Random Pivot

Quicksort's speed depends on the pivot splitting the array into two useful parts. A pivot that is always the smallest item splits n into nothing and n minus one, so the recursion runs n levels deep instead of log n and makes about n squared over 2 comparisons. "First element as pivot" hits this case on already sorted input, the most common input there is. Counted on 900 sorted items, a first-element quicksort made 404,550 comparisons, n squared over 2 almost exactly; on 5,000 sorted items it never finished, raising RecursionError when its depth passed Python's 1,000-frame limit.

A random pivot turns the bad split into a coin that must come up wrong at nearly every level. The expected cost is about 1.39 times n times the base-2 logarithm of n on every input, and Chapter 9 explains why randomness buys that guarantee. The same 5,000 sorted items took 70,229 comparisons with random pivots. Production quicksorts add a guaranteed fallback on top: GCC's C++ sort switches to heapsort if the recursion runs too deep, as Sorting in the Real World describes.

Stability

A stable sort keeps items with equal keys in their original order. Sort a list of books by year, then sort it stably by author, and each author's books stay in year order, because the second sort never reorders books whose authors are equal.

Merge sort is stable by construction: when the two front items are equal, it takes the one from the left run first. In-place quicksort is not, because its swaps carry items across long distances, past their equals. Languages that promise a stable sort ship a merge-based one for this reason. Python documents its sort as guaranteed stable, and Java documents its sort for objects the same way; both are Timsort.

What the Choice Costs in a Running System

Stability is what makes "click one column, then another" behave in every table on every screen: the second click sorts stably and the first click's order survives among the ties. Without it, rows with equal values shuffle every time the user sorts.

A quicksort with a predictable pivot is a denial-of-service surface when an attacker controls the input, the same shape as the hash flooding of Chapter 5. Douglas McIlroy's 1999 paper "A Killer Adversary for Quicksort" showed that an adversary who watches the comparisons can drive any deterministic quicksort to quadratic time on purpose. And merge sort's buffer is memory the service must have free at the moment the sort runs, on top of the data it is sorting.