heap-sort

Build a max-heap, then extract the maximum until one element remains.

best: O(n log n)
average: O(n log n)
worst: O(n log n)
space: O(1)

reference implementation

verified source·read-only

loading editor

brief

Heap sort treats the array as a complete binary tree, first sifting each internal node down until every parent is at least as large as its children, then repeatedly swapping the root — the maximum — to the end and shrinking the heap by one. Both phases work in place and the extractions are bounded by O(n log n), so heapsort sorts with no extra memory.

the math

The max-heap property

Every parent is at least as large as its children: $a[i] \ge a[2i+1]$ and $a[i] \ge a[2i+2]$ .
Build the heap by sifting down every internal node, from the last one back to the root.
Sifting down swaps a node with its larger child until the property holds again.

Sifting down

A sift-down follows one root-to-leaf path, so it touches at most $\lfloor \log_2 n \rfloor$ levels.
At each level the node is compared with its two children: at most two comparisons.
After a swap, the subtree below the previous root already satisfies the heap property.

Extracting the maximum

The root holds the maximum; swapping it to the end of the shrinking heap fixes its final position.
The new root is then sifted down to restore the heap property.
The sorted suffix grows from the right, one element per extraction.

Why O(n log n)

Building the heap with bottom-up sift-downs is $O(n)$ , not $O(n \log n)$ .
Each of the $n - 1$ extractions sifts down at most $\lfloor \log_2 n \rfloor$ levels.
Total: $O(n) + O(n \log n) = O(n \log n)$ , in the worst case and in place.

The sorted suffix

After each extraction the element left at the end is final and is marked sorted.
Once the heap holds a single element the whole array has been marked.
The last element never needs a comparison — it is the only one left.

▍ Heap Sort · small

requesting trace

· decoding trace

· replaying events

· mounting renderer

0/0

fun facts

J. W. J. Williams described the binary heap and heapsort in 1964 in Communications of the ACM.
Robert W. Floyd improved the heap-construction phase to O(n), giving the modern two-phase algorithm.
Heapsort sorts in place with O(1) auxiliary memory and never degrades past O(n log n).
It is the fallback in introsort: C++'s std::sort switches to heapsort when quicksort's recursion gets too deep.

heap-sortstep 0/00%spaceplay←→steppprojectorrreset