Cairn
algorithms · sorting · O(n log n) worst case · in-place

↩ back to Comparison Sorts

Heap Sort

A binary heap already knows how to answer "what's the biggest thing in here" in O(1), and how to restore that property in O(log n) after removing it. Heap sort is just that operation, run to exhaustion: turn the whole array into a max-heap in place, then repeatedly swap the root (the current maximum) with the last unsorted slot and shrink the heap by one. Do that n times and the array ends up sorted — ascending, and entirely within the original array. No pivot to pick badly like quicksort, no second buffer to allocate like merge sort: heap sort trades both of those away for a worst case that's always O(n log n), guaranteed, in O(1) extra space. See Pitfalls for what that trade actually costs.

Try it

Enter a comma-separated list of numbers, then step through the sort. The tan region is the active heap; the accent bar is the node currently being sifted down; a thin border marks the child it's being compared against. The first pass (build) turns the whole array into a max-heap without shrinking it. The second pass (extract) repeatedly swaps the root into the last heap slot — watch that slot turn the darker "sorted" shade and drop out of the heap — then sifts the new root back down.

Press Load, then Step through the sort.

Why it works

Two invariants, chained together. First, the max-heap property: every node is ≥ both its children, which forces the single largest value in the whole array to sit at index 0 — the same reasoning the heap page uses for its min-heap, just flipped. Second, once you swap that root into the last live slot and shrink the heap's boundary past it, that slot never has to be touched again: everything still inside the heap is, by the same property, ≤ the value that just left it. Sifting the new root down restores the max-heap property over the smaller heap, and the argument repeats. Each of the n extractions is O(log n) (a sift-down never travels further than the tree's height), so the whole sort is O(n log n) — and because every swap happens between two indices of the same array, no second array is ever allocated.

Reference implementation

The same array, max-heap version — built with bottom-up heapify (see the heap page for why that's O(n) instead of O(n log n)), then sorted by repeated extract-and-shrink. This is the exact scheme the demo above steps through, not a simplified stand-in:

function heapSort(arr) {
  const n = arr.length;
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) siftDown(arr, n, i);
  for (let end = n - 1; end > 0; end--) {
    [arr[0], arr[end]] = [arr[end], arr[0]];
    siftDown(arr, end, 0);
  }
  return arr;
}

function siftDown(arr, size, i) {
  while (true) {
    let largest = i;
    const l = 2 * i + 1, r = 2 * i + 2;
    if (l < size && arr[l] > arr[largest]) largest = l;
    if (r < size && arr[r] > arr[largest]) largest = r;
    if (largest === i) return;
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    i = largest;
  }
}

Pitfalls

Guaranteed asymptotics, worse constants. Heap sort's worst case is O(n log n) with no adversarial input that breaks it — a real advantage over quicksort's O(n²) worst case (see quicksort's Pitfalls). In practice, though, a well-tuned quicksort still runs faster on typical data — measured at roughly 1.6×–2× faster on random arrays on this site's own hardware, see Measuring the gap below — because sift-down jumps between indices i, 2i+1, and 2i+2 — far apart once the array is more than cache-line-sized — while quicksort's partition scan reads and writes mostly-adjacent memory. This is exactly why real standard-library sorts don't pick one and stop: C++'s std::sort is typically introsort — quicksort by default, falling back to heap sort only if the recursion depth blows past a bound that signals a bad pivot pattern. That fallback is the "switching strategy entirely" quicksort's own Pitfalls section mentions without naming: heap sort is the strategy it switches to, specifically because heap sort's worst case can't get any worse no matter how adversarial the input is.

It's not stable. Like quicksort, a heap-restoring swap can move one of two equal elements past the other with no tie-breaking rule — contrast with merge sort, where a deliberate <= in the merge step preserves original order. If stability matters, heap sort isn't it without extra bookkeeping (e.g. sorting index/value pairs and breaking ties on index).

Building the heap is a different loop from sorting it — mixing them up produces garbage. The build phase sifts down from the last non-leaf node to the root, over the whole array; the sort phase swaps the root out and sifts down over a shrinking array. Running the build loop's bounds during the sort phase (or vice versa) still executes without error — it just silently stops maintaining the heap property partway through, and the output looks plausible until you check it against a known-sorted reference.

Measuring the gap

The mechanism above (scattered sift-down jumps vs. quicksort's adjacent partition scan) predicts heap sort should lose more ground as arrays grow past whatever fits in cache — once every sift-down jump is a cache miss instead of an occasional one, the gap should widen rather than stay fixed. Both sorts here are the exact reference implementations from this page and quicksort's above, not reimplementations, run on freshly generated random arrays and timed with the browser's own clock.

Pick an array size, then click Measure — it generates a fresh random array, sorts independent copies of it with both algorithms above, and reports the median of 5 timed runs each.

Dozens of repeated runs (median of 5 each, rerun many times over) settled into a clear trend: roughly 1.6×–1.8× at 10,000 and 50,000 elements, climbing to 1.85×–1.95× at 150,000 and ~2× at 400,000 — a real, growing gap, not a fixed constant-factor penalty, consistent with the cache-miss explanation above. The smaller two sizes finish in only a couple of milliseconds, small enough that this VM's own background jitter occasionally swamps the signal — a handful of runs during testing landed as low as 1.0×–1.15× at 10,000–50,000 for no algorithmic reason, purely scheduling noise on shared hardware, while every run at 150,000 and above (tens of milliseconds, large enough to dwarf that noise) landed in the tight range just quoted. That's why the dropdown defaults to 150,000: large enough to show a reliable number on the first click rather than a coin flip. Worth being precise about what the reliable range does and doesn't show: it's wall-clock on one VM's JavaScript engine, not a hardware-independent law — a different engine, a typed array instead of a plain array, or a language with manual memory layout could all shift the exact ratio — but the direction (the gap widens with n, it doesn't shrink or flip) is the part the cache-locality argument actually predicts, and that part held at every size tried.

Complexity

Time: O(n log n) in every case — best, average, and worst — because building the heap is O(n) and each of the n extractions costs O(log n) regardless of the input's original order; there's no pivot choice or split size for an adversary to exploit. Space: O(1) extra — every swap is between two positions in the same array, no recursion stack (the sift-down loop above is iterative) and no merge buffer. That combination — worst-case guarantee and constant extra space — is strictly better than both merge sort (guaranteed but O(n) space) and quicksort (O(1)-ish space but no guarantee) on paper; see Measuring the gap above for the measured 1.6×–2× it still usually gives up in wall-clock time on real hardware.

For how this fits against the other eleven comparison sorts on this site — including when stability or write count matters more than either of these two — see Choosing a Comparison Sort.