Heapsort

A photo of Lake Issyk 120 pixels wide is 9600 pixels, and read row by row it is an ordinary array. Let us sort it by brightness with heapsort and redraw the array as a picture after each step. First a heap is built from the pixels, and the photo hardly changes. Then the brightest pixel of the heap goes to the end of the array again and again, and the picture drains into a gradient, from dark at the top to light at the bottom.

Building the heap took 13,841 comparisons, and after it 6828 pixels of the 9600 stand where they stood. The second half of the array is the leaves of the tree, and a leaf has nowhere to sink: it is moved only by a parent that sinks itself. All the rest of the time, 206 thousand comparisons out of 220,301, was taken by the second phase: 9599 times take out the largest and repair the heap. Tap any pixel at the bottom of the picture: its path to the top of the heap appears. The first step to the parent jumps across half the photo, the next across a quarter, and so on to the top left corner. These jumps are discussed in the section on speed.

The idea

A heap with the largest element on top can do one thing: give out the maximum quickly. So one can sort like this: build a heap from the array, swap its top with the last element of the heap, consider that element done, and repair the heap, which has become one element shorter. The heap lives at the start of the array and shrinks, while the sorted tail grows from the end. Both parts share the same array, so no extra memory is needed at all.

Everything rests on the structure of the binary heap: a complete binary tree laid out in an array without pointers, where the children of cell i lie in cells 2i + 1 and 2i + 2, and each parent is no smaller than its children. Sorting in ascending order needs a heap with the largest on top: the top goes to the end of the array, and the tail gathers from larger to smaller, from right to left. That is exactly why in the photo the brightest pixels appear first, in the bottom right corner.

Both phases come down to one operation, sifting down. An element standing higher than it should is swapped with the larger of its children until it is no smaller than both children or reaches a leaf.

1. Building. Sift down every node that has children, from the last such node (cell ⌊n/2⌋ − 1) to the root. When the turn comes to a node, both its subtrees are already heaps, and after sifting its subtree becomes a heap too. This method was proposed by Robert Floyd, and it costs fewer than 2n comparisons; the proof is in the article on the heap.
2. Extraction. For end = n − 1, …, 1: swap a[0] and a[end]; now a[end] is in its final place; the heap is a[0:end], and a stranger sits on its top; sift it down.

Step by step

The same sixteen strongest earthquakes of 2025 that the articles on merge sort and quicksort work on. Above, the array is drawn as a tree, below as it is, cell by cell. Watch where the new top comes from after each extraction.

Building the heap cost 24 comparisons, the extractions 55, 79 in all. Merge sort needed 46 comparisons on the same data, quicksort with a random pivot 98. Now look at the extractions more closely. The new top always comes from the last cell of the heap, that is, from the very bottom level, and something among the smallest lies there. It almost always has to sink to the bottom, and at each level it pays two comparisons: first the children with each other, then the larger child with it. The main speed-up of heapsort rests on this observation; we will return to it below.

Why n log n on any input

The word “any” matters here. Heapsort has no worst input, but it has no best one either. Insertion sort on an almost ordered array makes about n comparisons, Timsort finds ready runs, while heapsort does not care what it is given. Here are three inputs from the first scene, all made of the same pixels:

An array ordered in decreasing order is already a heap: building only makes sure of it, 9599 = n − 1 comparisons and not a single swap. But the second phase still takes the heap apart to the ground, and the difference between the best and worst input is eight per cent. An array sorted in increasing order, which quicksort with the first element as pivot turns into a square, costs here only 6% more than the photo.

A sort on heaps that notices existing order was built by Edsger Dijkstra in 1981: smoothsort. Instead of one binary heap it keeps a forest of heaps whose sizes are Leonardo numbers (1, 1, 3, 5, 9, 15, …, each one more than the sum of the two before), and on an ordered array it runs in O(n), and in the worst case in O(n log n), with no extra memory. It is noticeably more complicated and rarely met in practice; one example is qsort in the musl library.

Almost half the comparisons are unnecessary

Back to the observation from the second scene. After the swap the top of the heap is the former last leaf, one of the smallest elements. Half the nodes of a heap are leaves and a quarter their parents, so a random small element will almost certainly sink to the very bottom or to the level above it. Yet ordinary sifting compares it with the larger child at each level along the way, checking whether it is time to stop, although it almost never is.

Hence the bottom-up sift. First do not look at the sinking element at all: go down from the top to a leaf, each time moving to the larger of the children, which is one comparison per level. This gives a path along which the elements do not increase; the sinking element will end up somewhere on it. Look for its place by going up from the leaf: one or two comparisons are usually enough, since the place is near the bottom. Then all the elements of the path from the top to the place found move up a level, and the sinking element takes the freed place. The swaps are exactly the same as in ordinary sifting, the output order is the same, and there are 40% fewer comparisons.

Switch the sift in the first scene to “bottom-up”. On the photo that is 132,979 comparisons instead of 220,301, 1.05 n log₂ n instead of 1.73. Almost all the saving comes in the second phase. In building, the new technique even loses: 17,978 comparisons against 13,841. There the node being sifted comes from the middle of the array, an ordinary one, not among the smallest, and it often stops at once, while going down to a leaf still spends comparisons at every level.

Donald Knuth gives this technique in an exercise to section 5.2.3 of the third volume of “The Art of Computer Programming”, where heapsort is analysed, and attributes it to Floyd. It was analysed in detail by Ingo Wegener: a 1993 paper with the telling title “BOTTOM-UP-HEAPSORT, a new variant of HEAPSORT beating, on an average, QUICKSORT (if n is not very small)” showed that the comparisons average about n log₂ n, and in the worst case at most 1.5 n log₂ n + O(n). Beating means in the number of comparisons: quicksort with a random pivot needs about 1.39 n log₂ n on average.

Since 2019 this is how the Linux kernel sorts: the sort() function in lib/sort.c is heapsort with a bottom-up sift. The author of the change, George Spelvin, estimated the gain in the commit message: it used to be 2n log₂ n − 3n comparisons on average, now n log₂ n + 0.37n. In the kernel a comparison is a call through a function pointer, and after the defences against Spectre attacks such calls became expensive, so a comparison saved is worth noticeably more than a couple of extra steps through the array.

Code

Heapsort in one function: an inner sift function and two loops. The comparison counter is split into the two phases; these are the same 24 and 55 as in the earthquake scene.

Instability shows at once: of the four earthquakes of magnitude 7.4, not one has kept its place among equals. Swapping the top with the end of the heap carries an element across the whole array, past its equals, and this sort remembers no order among equals:

  7.4: 07-20 10-10 05-02 09-13  <- out of date order

The second program is the whole first scene: it reads the same photo in the sandbox, sorts its pixels with both sifts on three inputs and checks that the results agree pixel for pixel.

What it costs

By the table heapsort looks the best of the three: the guarantee of merge sort and the memory of quicksort. But the benchmark says otherwise. Below are Python and Go, random numbers, heapsort in two variants, quicksort from its article and the built-in sort.

In Go, while the array is small, heapsort runs level with quicksort: on 16 thousand numbers they take the same time. After that it falls behind, the more so the bigger the array: on 256 thousand and on a million by 1.2 times, on four million by 2.4. It makes more comparisons, but their ratio to quicksort’s comparisons hardly depends on n. The growing lag comes from memory.

Quicksort reads the array in order: two pointers move towards each other, and the processor prefetches the next cells into the cache. Heapsort jumps: from cell i to 2i + 1, from there to 4i + 3, and on the lower levels each step takes it megabytes further. Tap a pixel in the bottom row in the first scene: its path to the top flies across the whole picture, and neighbours in the tree are almost never neighbours in memory. While the array lies wholly in the processor cache, the jumps are free; when it stops fitting, almost every step down the tree is a cache miss. More on this in the article on cache-friendly data.

The bottom-up sift does not help in these measurements: comparing two float64 numbers costs less than an extra pass along the path, and in Go it is 1.3–1.8 times slower than the ordinary one. Saving comparisons pays off when a comparison is expensive: a call through a function pointer, as in the Linux kernel, a comparison of strings or of records by several fields. In Python both heapsorts are one and a half to three times slower than quicksort: there the time goes on the interpreter and cache misses never come into it, while the built-in sort, written in C, beats them all by 10–40 times.

Where it works

Insurance for quicksort. Quicksort is good at everything except its worst case. Introsort by David Musser (1997) is a quicksort that watches the recursion depth and, if it exceeds a limit, finishes the remaining piece with heapsort. This is how std::sort in libstdc++ is built: the depth limit is 2⌊log₂ n⌋, and the fallback is the partial sort function, which on the whole piece is exactly heapsort. Array.Sort in .NET is built the same way: its documentation says that when the number of partitions exceeds 2 log n, the method switches to heapsort. In Go since version 1.19 sorting is done by pdqsort: it counts bad partitions, where the smaller part is shorter than an eighth of the piece, and after ⌊log₂ n⌋ + 1 such partitions it too calls heapsort. In Rust sort_unstable is based on ipnsort, which according to its documentation combines the fast average case of quicksort with the fast worst case of heapsort. In Java the dual-pivot quicksort for arrays of numbers, rewritten by version 14, also switches to heapsort when the recursion is too deep. On ordinary data this fallback never fires; it is needed against data chosen by an adversary, built for example by McIlroy’s attack.

Where neither recursion nor memory is allowed. In an operating system kernel the stack is small, allocating memory during a sort is undesirable, and the time must be predictable. So sort() in the Linux kernel is heapsort, and a comment in the code says plainly why not quicksort: its worst case is n², which can be triggered on purpose, plus extra memory. The same applies to embedded systems and real-time code.

The k best. If what is needed is not the whole order but only the k largest, heapsort is stopped after k extractions: O(n + k log n). And std::partial_sort in C++ does the reverse: it keeps a heap of k elements, passes the rest through it, and then sorts the heap itself. That is a separate topic, the article “Top-k: the k best”.

History

Heapsort appeared in June 1964 in Communications of the ACM: the algorithms section carried a short note by J. W. J. Williams, “Algorithm 232: Heapsort”, with a program in Algol. The heap itself appeared in it too, described as a useful structure in its own right. Williams built the heap by adding the elements one at a time, in O(n log n). In December of the same year Robert Floyd printed “Algorithm 245: Treesort 3” in the same journal, the sort almost in the form in which it is written today, with the heap built bottom up in linear time. Floyd had published tree sorts before, the first, “Algorithm 113: Treesort”, came out in 1962, and they can be seen as steps towards heapsort. The story of Williams is in the course chapter “Who is next”.

After that heapsort had two paths. One was saving comparisons: the bottom-up sift, described by Knuth with a reference to Floyd and analysed by Wegener in 1990–1993. The other was noticing existing order: Dijkstra’s smoothsort of 1981. And in 1997 Musser found it the role in which it still works: insurance inside quicksort.

Problems

In the first problem the sort was stopped right after building the heap, and you have to work out where in the heap the k-th largest element can be: this is a question about the heap property, not about code. The second is to implement the bottom-up sift carefully and count how many comparisons it saves.