Heapsort

What this chapter covers

Heapsort is the sort that looks best on paper: O(n log n) guaranteed, like merge sort, but in place with O(1) extra space, like quicksort — the good properties of both with the drawbacks of neither. It gets there through a data structure we'll study in full two chapters from now, the binary heap: a tree cleverly flattened into an array, where you can always grab the largest element in O(log n). Heapsort builds that heap inside the array, then repeatedly pulls the maximum to the end. This chapter builds it, watches the sorted region grow as maxima are extracted, and confronts the puzzle of why a sort with the best asymptotics is rarely the fastest in practice.

A bit of history

Heapsort arrived in 1964, and with it the heap. J. W. J. Williams published the algorithm and introduced the binary heap as its engine; in the same year Robert Floyd showed that the heap could be built in linear time, not the O(n log n) you'd expect — a result we'll prove below because it's genuinely surprising. Together they gave the first sort that was simultaneously in-place and guaranteed O(n log n), settling a real question of the era: could you have both without merge sort's memory or quicksort's worst case? You could. Heapsort has stayed slightly in the shadow of quicksort ever since — it's usually a bit slower — but it never disappears, because it's the safety net: the introsort in your C++ and Rust standard libraries is quicksort that switches to heapsort the moment a bad pivot threatens, precisely because heapsort's O(n log n) is unconditional.

The intuition

A binary heap is a tree squashed into an array. Put the root at index 0; then for any node at index i, its two children sit at 2i+1 and 2i+2. That arithmetic is the whole trick — the parent-child structure is implied by the indices, so a heap needs no pointers and lives entirely in the array. A max-heap adds one rule: every parent is at least as large as its children, which means the largest element of the whole heap is always at the root, index 0.

Heapsort uses that in two phases. First, rearrange the array so it satisfies the heap rule — build the heap. Now the maximum is at the front. Swap it with the last element: the maximum is now in its final sorted position at the end, and the array is a heap again except the root, which is probably too small. "Sift" that root down — swap it with its larger child, repeatedly, until it settles — and the heap is restored over the remaining, smaller region. Repeat: each step moves the current maximum to the end and shrinks the heap by one. The sorted region grows from the right, one extracted maximum at a time, until the whole array is sorted.

Complexity: how it scales

Each sift-down walks a path from a node to a leaf, which is at most the tree's height, $O(\log n)$. There are n extractions, each doing one sift-down, so the extraction phase is $O(n \log n)$. Building the heap is $O(n)$ — surprisingly, not $O(n \log n)$, for the reason in the deep-dive below — so it doesn't change the total. And it's all in place: $O(1)$ extra space, just swaps within the array. Best, average, and worst case are all $O(n \log n)$, because the structure of the work doesn't depend on the input values.

That last point is heapsort's quiet superpower, and the consistency chart shows it. The same heapsort runs on random, already-sorted, and reverse-sorted input of the same size in essentially identical time — where quicksort's naive pivot blew up 141× on sorted input, heapsort doesn't flinch:

What it's good at, what it isn't

Heapsort is the sort for when the worst case is unacceptable and memory is scarce at the same time. Merge sort guarantees O(n log n) but needs O(n) memory; quicksort is in place but has an O(n²) worst case; heapsort alone gives you O(n log n) worst-case and O(1) space. That combination is why it's the fallback inside introsort and why it shows up in real-time and embedded systems that can't tolerate either an allocation or a quadratic blowup.

The reason it isn't the default, despite the best asymptotics, is the cache. Heapsort jumps around the array — a parent at index i and its child at 2i+1 can be far apart in memory — so it thrashes the CPU cache in a way that quicksort's local, sequential swaps don't. Big-O counts those two accesses the same; the hardware charges wildly different prices. The result is that heapsort is usually noticeably slower than quicksort or a tuned merge sort in practice, even though all three are O(n log n). It's also not stable. So heapsort is the choice you make for its guarantee, not its speed.

The data, or the inputs

The face-off sorts random integers against heapq and Timsort. The consistency chart runs heapsort on random, sorted, and reversed input to show it has no bad case — the direct contrast to quicksort's worst-case chart. And the animation runs heapsort on twelve elements, showing the extraction phase: the sorted region growing from the right as each maximum is locked into place.

Build it, one function at a time

The whole sort is two phases — build the heap, then extract the max n−1 times:

def heapsort(a, probe=None):
    """O(n log n) in every case, in place. Two phases: build a max-heap (so the
    largest element is at the front), then repeatedly swap the front to the end of
    the unsorted region and sift the new front back down. The sorted region grows
    from the right as each maximum is locked into place."""
    a = list(a)
    n = len(a)
    # Phase 1 — build the max-heap bottom-up: sift every non-leaf down. This is
    # O(n), tighter than it looks (most nodes are near the bottom).
    for start in range(n // 2 - 1, -1, -1):
        _sift_down(a, start, n)
    if probe is not None:
        probe.append({"arr": list(a), "end": n})
    # Phase 2 — extract the max n-1 times. Each extraction is O(log n).
    for end in range(n - 1, 0, -1):
        a[0], a[end] = a[end], a[0]      # the max moves to its final position
        _sift_down(a, 0, end)            # restore the heap over the shrunk region
        if probe is not None:
            probe.append({"arr": list(a), "end": end})
    return a

Both phases lean on one operation, sift-down: restore the heap property at a node by sinking it past any larger child. The index arithmetic — children at 2i+1 and 2i+2 — is where the array-as-tree idea becomes code:

def _sift_down(a, i, size):
    """Restore the max-heap property at index i within a[0:size]: while a node is
    smaller than its largest child, swap them and keep sinking. Children of i are at
    2i+1 and 2i+2 — the parent/child arithmetic is the whole reason a heap needs no
    pointers."""
    while True:
        largest = i
        left, right = 2 * i + 1, 2 * i + 2
        if left < size and a[left] > a[largest]:
            largest = left
        if right < size and a[right] > a[largest]:
            largest = right
        if largest == i:
            return
        a[i], a[largest] = a[largest], a[i]
        i = largest

Watch it work

Here's the extraction phase on twelve bars. The first frame shows the built max-heap — the largest element is at the front (orange), the rest satisfy the heap rule (blue). Then each frame extracts the current maximum: it swaps to the boundary and joins the sorted region on the right (green), and a new maximum sifts up to the front for next time. Step through it and watch the green sorted tail grow leftward, one maximum per step, while the blue heap shrinks — the array sorting itself in place with no second array anywhere:

The complete code

Both versions in one place — flip between them. The from-scratch tab is our in-place heapsort. The library tab is heapq, Python's binary heap: heapify a list and pop everything off and you get sorted order — the same algorithm in C. (For real sorting you'd still call sorted; heapsort's role in the library is the introsort fallback.)

"""Heapsort — the O(n log n) sort that's guaranteed like merge sort but in place
like quicksort. It works by turning the array into a binary max-heap and then
repeatedly pulling out the maximum.

A binary heap is a tree flattened into an array: the children of index i live at
2i+1 and 2i+2, and every parent is at least as large as its children (a max-heap).
That layout means no pointers — the array IS the tree — and it's the structure this
chapter uses to sort and the one the heaps chapter later studies in its own right.
"""


# region: heapsort
def heapsort(a, probe=None):
    """O(n log n) in every case, in place. Two phases: build a max-heap (so the
    largest element is at the front), then repeatedly swap the front to the end of
    the unsorted region and sift the new front back down. The sorted region grows
    from the right as each maximum is locked into place."""
    a = list(a)
    n = len(a)
    # Phase 1 — build the max-heap bottom-up: sift every non-leaf down. This is
    # O(n), tighter than it looks (most nodes are near the bottom).
    for start in range(n // 2 - 1, -1, -1):
        _sift_down(a, start, n)
    if probe is not None:
        probe.append({"arr": list(a), "end": n})
    # Phase 2 — extract the max n-1 times. Each extraction is O(log n).
    for end in range(n - 1, 0, -1):
        a[0], a[end] = a[end], a[0]      # the max moves to its final position
        _sift_down(a, 0, end)            # restore the heap over the shrunk region
        if probe is not None:
            probe.append({"arr": list(a), "end": end})
    return a
# endregion


# region: sift_down
def _sift_down(a, i, size):
    """Restore the max-heap property at index i within a[0:size]: while a node is
    smaller than its largest child, swap them and keep sinking. Children of i are at
    2i+1 and 2i+2 — the parent/child arithmetic is the whole reason a heap needs no
    pointers."""
    while True:
        largest = i
        left, right = 2 * i + 1, 2 * i + 2
        if left < size and a[left] > a[largest]:
            largest = left
        if right < size and a[right] > a[largest]:
            largest = right
        if largest == i:
            return
        a[i], a[largest] = a[largest], a[i]
        i = largest
# endregion

"""Python's `heapq` module is a binary heap (a min-heap) in C. Heapifying a list and
popping everything off yields sorted order — that's heapsort, essentially. And
`sorted` (Timsort) is what you'd actually call. Heapsort itself rarely appears as a
standalone library sort, but it's the guaranteed-O(n log n) fallback inside introsort
(the quicksort variant from last chapter), so it's always one step away.

The face-off is our heapsort against `heapq`-based sorting and against `sorted`.
"""
import heapq


# region: heapq_sort
def heapq_sort(a):
    """heapify + pop-all: a min-heap yields ascending order. Same idea as heapsort,
    implemented in C — though it builds a new list rather than sorting in place."""
    h = list(a)
    heapq.heapify(h)
    return [heapq.heappop(h) for _ in range(len(h))]
# endregion


# region: sort_builtin
def sort_builtin(a):
    """Timsort — the sort you'd actually reach for."""
    return sorted(a)
# endregion

Scratch vs library

Sorting 80000 integers, our heapsort took about 148 ms against Timsort's 7.5 ms — about 20 times slower, and notably slower than our own quicksort (61 ms) and merge sort (86 ms) on the identical task. That ordering is the chapter's real lesson: heapsort has the best Big-O profile of the three yet loses the practical race, because its cache-hostile access pattern carries a constant the others don't. But look back at the consistency chart before writing it off — heapsort's numbers were flat across random, sorted, and reversed input, where quicksort exploded. Heapsort trades a bit of everyday speed for a guarantee that holds against any input, including one an adversary picks. That's exactly the trade a library makes when it uses quicksort for speed but keeps heapsort in reserve for safety.

Where you'll actually meet it

Heapsort itself is the fallback in introsort, so it runs whenever std::sort or Rust's unstable sort detects a quicksort pivot going bad — you use it without seeing it, as the guarantee behind the fast path. But the heap underneath is the real export of this chapter: the same structure, used for extraction rather than sorting, is the priority queue two chapters from now — the engine behind Dijkstra's shortest paths, Huffman coding, event simulations, and the top-k queries that heapq.nlargest answers. Heapsort is where the heap first earns its keep; the heaps chapter is where it becomes a tool in its own right.

Takeaways

Heapsort builds a binary max-heap in the array — children at 2i+1 and 2i+2, no pointers — then extracts the maximum n−1 times, growing a sorted region from the right. It's $O(n \log n)$ in every case and $O(1)$ in space, the only comparison sort with both guarantees, which is why it's the trusted fallback. Its catch is entirely in the constant: a cache-hostile access pattern makes it slower than quicksort in practice, a vivid case of Big-O and reality parting ways.

That completes the comparison sorts, and with them a hard limit: any sort that works by comparing elements needs $\Omega(n \log n)$ comparisons — you can't do better in general. The next chapter escapes that bound by not comparing: when the keys are bounded integers, counting and radix sort run in $O(n)$, beating the "impossible" limit by using the keys as array indices instead of comparing them.