Heap sort
mediumThe tree and the array below it are the same memory - watch a swap change both at once. The only sort here with an O(n log n) guarantee and O(1) extra space.
O(n log n)Average O(n log n)Worst O(n log n)Space O(1)Not stableIn placeSaved in this browser - no sign-up, nothing sent anywhere.
How heap sort works
Selection sort with a better memory. Both repeatedly extract the maximum, but selection sort re-scans everything for each one at O(n) a round. A max-heap remembers most of the comparison work between rounds, so the next maximum costs O(log n). The heap lives inside the array itself - node i's children sit at 2i + 1 and 2i + 2, no pointers anywhere.
Phase 1 builds the heap bottom-up: start at the last parent, index n/2 - 1, and sift each node down toward the leaves. That order makes building O(n), not O(n log n) - half the nodes are leaves and sift nowhere. Phase 2 repeats: swap the root, always the maximum, into the last unsorted slot, shrink the heap by one, sift the new root down to restore order.
The result is the only sort here with both an O(n log n) worst-case guarantee and O(1) extra space - no buffer, no recursion. It still loses to quicksort on wall-clock time because sift-down doubles the index every hop, jumping across memory and missing cache. So its role in practice is the safety net: introsort falls back to it when quicksort's recursion goes bad.
Step by step
- Sort [4, 10, 3, 5, 1]. As a tree: root 4 with children 10 and 3; 10's children are 5 and 1.
- Build from the last parent, index 1: 10 already beats 5 and 1. At the root, 4 < 10, so they swap; 4 then swaps with 5 below: [10, 5, 3, 4, 1]. Max-heap built.
- Extraction 1: swap root 10 with the last slot: [1, 5, 3, 4, 10]. 10 is final. Sift 1 down past 5 and 4: [5, 4, 3, 1, 10].
- Extraction 2: swap 5 out: [1, 4, 3, 5, 10]; 1 sifts below 4: [4, 1, 3, 5, 10].
- Extraction 3: swap 4 out: [3, 1, 4, 5, 10]; 3 already beats 1, so the heap holds.
- The last swap gives [1, 3, 4, 5, 10]. The sorted region grew right to left, one maximum per round.
Complexity
| Best case time | O(n log n) |
|---|---|
| Average time | O(n log n) |
| Worst case time | O(n log n) |
| Space | O(1) |
Building the heap is O(n); each of the n extractions costs O(log n).
Reference implementation
Python
def heap_sort(a):
n = len(a)
for i in range(n // 2 - 1, -1, -1): # build a max-heap bottom-up
sift_down(a, i, n)
for end in range(n - 1, 0, -1):
a[0], a[end] = a[end], a[0] # root is the max
sift_down(a, 0, end)
return a
def sift_down(a, i, size):
while 2 * i + 1 < size:
c = 2 * i + 1
if c + 1 < size and a[c + 1] > a[c]:
c += 1
if a[i] >= a[c]:
break
a[i], a[c] = a[c], a[i]
i = cJavaScript
function heapSort(a) {
const n = a.length;
for (let i = (n >> 1) - 1; i >= 0; i--) siftDown(a, i, n);
for (let end = n - 1; end > 0; end--) {
[a[0], a[end]] = [a[end], a[0]];
siftDown(a, 0, end);
}
return a;
}
function siftDown(a, i, size) {
while (2 * i + 1 < size) {
let c = 2 * i + 1;
if (c + 1 < size && a[c + 1] > a[c]) c++;
if (a[i] >= a[c]) break;
[a[i], a[c]] = [a[c], a[i]];
i = c;
}
}Java
static void heapSort(int[] a) {
int n = a.length;
for (int i = n / 2 - 1; i >= 0; i--) siftDown(a, i, n);
for (int end = n - 1; end > 0; end--) {
int t = a[0]; a[0] = a[end]; a[end] = t;
siftDown(a, 0, end);
}
}
static void siftDown(int[] a, int i, int size) {
while (2 * i + 1 < size) {
int c = 2 * i + 1;
if (c + 1 < size && a[c + 1] > a[c]) c++;
if (a[i] >= a[c]) break;
int t = a[i]; a[i] = a[c]; a[c] = t;
i = c;
}
}Worth noticing
The array *is* the tree
There are no pointers anywhere. Node i's children live at 2i+1 and 2i+2, so the tree above and the bars below are two views of exactly the same memory. Watch a swap change both at once.
Building the heap is O(n), not O(n log n)
The build phase starts at the last parent and works backwards. Most nodes are near the bottom and sift down almost no distance, so the total is linear - a genuinely surprising result worth checking against the comparison counter.
Selection sort with a better memory
Heap sort repeatedly extracts the maximum, exactly like selection sort. The difference is that a heap remembers most of the comparison work between rounds, so finding the next maximum costs O(log n) instead of O(n).
O(n log n) worst case with O(1) extra space
The only algorithm here with both guarantees. It loses to quicksort in practice because it jumps around memory - every sift-down doubles the index and blows the cache line.
Common pitfalls
- Building the heap top-down with sift-up, which costs O(n log n). Bottom-up sift-down from the last parent is what makes the build phase linear.
- Passing the wrong heap size after an extraction. The sift after swapping into slot end must cover exactly end elements - one too many and the just-placed maximum gets sucked back in.
- Skipping the c + 1 < size check before comparing the right child - the last parent often has only a left child, and the read runs past the heap boundary.
- Sifting toward the left child unconditionally instead of the larger child. The heap property breaks silently and the bug surfaces as an almost-sorted array.
- Expecting stability: the root-to-end swaps and sift paths shuffle equal values freely. Heap sort is unstable by construction.
Where it is used
- Introsort's escape hatch: C++ std::sort switches to heap sort when quicksort recursion exceeds its depth budget, preserving the O(n log n) guarantee.
- The Linux kernel's in-kernel sort() is heap sort - no recursion, no allocation, bounded worst case.
- Top-k selection: build a heap in O(n), extract k times for O(n + k log n) - cheaper than fully sorting.
- The interview double feature: implement siftDown, then prove the build phase is O(n).
Frequently asked questions
What is the time and space complexity of heap sort?
O(n log n) in the best, average, and worst case: building the max-heap costs O(n), then each of the n extractions pays an O(log n) sift-down. Space is O(1) - the heap is the array itself, and the iterative sift needs no stack. No input changes the shape of the work.
Why is building a heap O(n) and not O(n log n)?
Because the work is bottom-heavy in your favour. Half the nodes are leaves and sift zero levels, a quarter sift at most one, an eighth at most two. The total is n/4 × 1 + n/8 × 2 + n/16 × 3 and so on, a series that converges to about n - not the n log n a per-node worst case suggests.
Is heap sort stable?
No. Every extraction swaps the root with the last heap slot, and every sift-down swaps parents with children along a path - both moves carry values past equal elements without ever comparing against them. Equal keys can finish in any relative order, so use merge sort when input order must survive.
If heap sort guarantees O(n log n), why is quicksort still faster in practice?
Memory access patterns. Quicksort's partition scans the array sequentially, so nearly every access hits cache; heap sort's sift jumps from index i to 2i + 1, roughly doubling the address every step and missing cache at each level. That constant factor typically makes heap sort two to three times slower on the same data.