Why Heapsort Is Not Stable

Heapsort is not stable: two items with equal keys can come out in the opposite order to the one they went in, because the swap that moves the root to the end of the heap carries it over items it was never compared with. This card shows that happening on four records, says what heapsort's O(1) space buys in exchange, and when the trade is worth it.

A sort is stable when items with equal keys keep their input order. Four records, each a name and a score, were heapsorted by score in a run. Ana and Cai both scored 3, and Ana came first in the input.

The scores came out in order, 1 2 3 3, but Cai now comes before Ana. The build left Ana at the root, since a sift-down only swaps a parent with a strictly larger child, and the first extraction swapped the root with the last item of the heap, sending Ana from index 0 straight to index 3, over Cai at index 2. A stable sort would have printed Ben, Dee, Ana, Cai. Instability is not an error in the order of the keys: the scores are sorted either way. It matters only when the input order carried information, such as an earlier sort by name.

You can make heapsort keep ties in order by sorting on the pair of key and input position, but storing a position for every item costs O(n) extra memory, which gives up the one thing heapsort offers that the stable merge sort does not.

That thing is O(1) extra space together with O(n log n) on every input. Heapsort is slower than quicksort on average, though, and a run that sorted 1,000 numbers with each showed it.

Heapsort made between 1.5 and 1.8 times as many comparisons on every input, because each level of a sift-down compares the two children with each other and then the larger with the parent. It also jumps around the array: a sift-down goes from index i to 2i + 1, far apart in memory once the array is large, where a partition walks the array in order. So heapsort earns its place where memory is fixed and the worst case matters more than the average, as in embedded systems and as the fallback inside an introsort, and not as the default sort for general data.