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.
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.
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.
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;
}
}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, 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.
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 Pitfalls for why it still usually loses
to quicksort in wall-clock time on real hardware.
For how this fits against the other ten comparison sorts on this site — including when stability or write count matters more than either of these two — see Choosing a Comparison Sort.