A max-heap always hands you the largest remaining key. Heapsort uses that to sort an array in place. First rearrange the array into a max-heap. Then, again and again, swap the maximum to the end and shrink the heap by one. The array splits into two parts: a heap that shrinks, and a sorted part that grows from the right.
This builds on Binary heaps: the array layout (children of i at 2i + 1 and 2i + 2) and sift-down (swap a key with its larger child until both children are smaller).
Any array can be drawn as a complete tree, so only heap order needs fixing. The leaves (indices ⌊n/2⌋ to n − 1) are already one-key heaps. So start at the last node that has a child, index ⌊n/2⌋ − 1, and sift each node down, working back to the root. Each node is sifted after its subtrees are already heaps, which is exactly what sift-down needs.
This takes only O(n), not O(n log n): half the nodes are leaves and don't move, a quarter can drop at most one level, an eighth at most two, and so on.
Repeat until one key is left in the heap. It is the smallest, already at index 0.
| Heapsort | |
|---|---|
| Time | O(n) to build, plus n − 1 sift-downs of O(log n): O(n log n), even in the worst case. |
| Extra space | O(1): everything happens inside the array. |
| Stable? | No: equal keys can end up in a different order. |
Quicksort is usually faster in practice, and mergesort is stable. Heapsort's strength is its guaranteed O(n log n) with no extra memory, which is why introsort falls back to it.