Heapsort

August 2026 · 21 min read

Heapsort is what you get when you notice that a heap hands you the minimum in O(log n) and you need n of them. It is the only comparison sort that is simultaneously O(n log n) in the worst case and O(1) in extra space — quicksort gives up the first, mergesort the second. And yet it is rarely the sort anyone actually runs. Understanding why is more instructive than the algorithm itself.

The Algorithm

The clever part is the in-place trick. To sort ascending you use a max-heap, not a min-heap:

1. make_heap over the whole array — O(n) by Part 4.
2. Swap a[0] (the maximum) with the last unsorted slot. The maximum is now in its final sorted position.
3. Shrink the heap boundary by one and sift_down(0) over the smaller region.
4. Repeat until the heap holds one element.

The array is split into a shrinking heap prefix and a growing sorted suffix, and the two never need extra storage because every element removed from the heap lands exactly where the sorted region begins.

void heapsort(std::vector<int>& a) {
    std::size_t n = a.size();
    if (n < 2) return;

    for (std::size_t i = n / 2; i-- > 0; )      // build max-heap, O(n)
        sift_down(a, i, n);

    for (std::size_t end = n; end-- > 1; ) {    // extract, O(n log n)
        std::swap(a[0], a[end]);                // max to its final slot
        sift_down(a, 0, end);                   // re-heapify the prefix
    }
}

void sift_down(std::vector<int>& a, std::size_t i, std::size_t n) {
    int value = a[i];
    for (;;) {
        std::size_t l = 2 * i + 1;
        if (l >= n) break;
        std::size_t c = (l + 1 < n && a[l + 1] > a[l]) ? l + 1 : l;  // LARGER child
        if (a[c] <= value) break;
        a[i] = a[c];
        i = c;
    }
    a[i] = value;
}

Note sift_down takes n as an explicit bound rather than reading a.size(). That parameter is the heap boundary, and it is what keeps the sorted suffix untouched.

A Trace

Sorting [4, 10, 3, 5, 1]. The vertical bar marks the heap/sorted boundary.

build max-heap        [10, 5, 3, 4, 1 |]

swap 10 <-> 1         [1, 5, 3, 4 | 10]
sift_down             [5, 4, 3, 1 | 10]

swap 5 <-> 1          [1, 4, 3 | 5, 10]
sift_down             [4, 1, 3 | 5, 10]

swap 4 <-> 3          [3, 1 | 4, 5, 10]
sift_down             [3, 1 | 4, 5, 10]

swap 3 <-> 1          [1 | 3, 4, 5, 10]

result                [1, 3, 4, 5, 10]

The sorted region grows right to left, always receiving the largest remaining element. No auxiliary array is ever allocated.

Why a Max-Heap for Ascending Order

A frequent stumble. With a min-heap you would extract the smallest first — but the slot freed by shrinking the heap is at the end of the array, so the smallest element would land at the far right. You would end up with a descending array, and reversing it costs another pass.

A max-heap puts the largest element at the rightmost free slot, then the second-largest just left of it, and so on. The sorted order falls out naturally. Rule: max-heap for ascending, min-heap for descending.

Complexity

The worst case equals the average case, with no pathological inputs and no randomisation needed. Quicksort cannot promise that; its O(n²) worst case is reachable by adversarial input, which is a genuine security consideration for anything sorting attacker-controlled data.

So Why Is Heapsort Rarely Used?

Because asymptotic complexity is not running time, and heapsort loses on three of the constants that matter.

Cache hostility. This is the big one. Sift-down jumps from index i to 2i+1 — a stride that doubles at every level. Once the array exceeds cache size those jumps become misses, and each level of every sift-down is a fresh miss. Quicksort, by contrast, partitions with two linear scans, which is the friendliest possible access pattern for a hardware prefetcher. On large arrays quicksort routinely runs 2–3x faster than heapsort despite the identical asymptotic bound.

Branch misprediction. The “which child is larger” comparison is essentially random on unsorted data, so it mispredicts about half the time, and it happens at every level of every sift-down.

It is not stable. Equal elements are reordered arbitrarily by the swaps. If you are sorting records by one field and need the previous order preserved within ties, heapsort silently destroys it.

Where Heapsort Actually Ships: introsort

Heapsort's real job in production is as a safety net. std::sort in libstdc++ and libc++ implements introsort:

1. Run quicksort, for its excellent cache behaviour and constants.
2. Track recursion depth. If it exceeds 2 * log2(n) — evidence that pivot selection is going badly and the O(n²) case is unfolding — abandon quicksort and finish that subrange with heapsort.
3. Below a small threshold (typically 16 elements), switch to insertion sort, which wins on tiny arrays.

This is why std::sort can guarantee O(n log n) worst case — a guarantee it has held since C++11 — while still running at quicksort speed on ordinary input. Heapsort supplies the guarantee precisely because its worst case is its average case and it needs no extra memory to deliver that. It is the algorithm you keep for the bad days.

The Genuinely Useful Cousin: partial_sort

When you want the smallest k of n in sorted order, sorting everything is wasteful. std::partial_sort is heapsort stopped early:

#include <algorithm>

std::partial_sort(v.begin(), v.begin() + k, v.end());
// v[0..k) now holds the k smallest, sorted; the rest is unspecified
// cost: O(n log k), not O(n log n)

Internally it builds a max-heap over the first k elements, then scans the remaining n-k, replacing the root whenever a smaller element appears. That is the bounded-heap pattern, and it is the subject of the next post.