Build a max-heap, then repeatedly swap the root to the end and re-sink. Guaranteed O(n log n) with O(1) extra space — the only common sort that gets both at once.
Controls
array size10
# phase 1: heapifyfor i in range(n//2-1, -1, -1):
sift_down(a, i, n)
# phase 2: extractfor i in range(n-1, 0, -1):
a[0], a[i] = a[i], a[0]
sift_down(a, 0, i)
Heap and Sorted Region
step 0
Insight
Two phases: heapify the array into a max-heap in O(n), then repeatedly swap the root to the sorted tail and sift down, n times at O(log n) each.
phase–
comparisons0
swaps0
extra memoryO(1)
Complexity
Time (all cases)O(n log n)
SpaceO(1)
StableNo
Heap Sort
The sort that never has a bad day — and never wins a benchmark either.
Quick Context
Heap sort turns the array into a max-heap, then repeatedly moves the largest element to the end. It sorts in place with a guaranteed O(n log n) in every case — best, average and worst.
Phase 1: Heapify in O(n)
Starting from the last non-leaf node and working backwards, sift each element down. Leaves are already valid heaps of size one, so half the array needs no work at all.
It looks like it should be O(n log n), but it is O(n). Most nodes are near the bottom and can only sink a short distance; only the root can travel the full height. Summing the actual work gives a series that converges to O(n).
Phase 2: Extract n Times
The maximum is always at index 0. Swap it with the last element of the heap, shrink the heap by one, and sift the new root down to restore the heap property.
The array splits into two regions: an unsorted heap at the front and a growing sorted tail at the back. Watch the green region grow from the right as you step.
Each extraction costs O(log n) and there are n of them → O(n log n). Adding the O(n) heapify leaves O(n log n) overall.
Why It Loses to Quick Sort in Practice
Heap sort has better worst-case guarantees than quick sort (which can degrade to O(n²)) and uses less memory than merge sort (which needs O(n)). Yet quick sort is usually faster in the real world.
The reason is cache locality. Sifting jumps between indices i, 2i+1 and 2i+2 — wildly scattered addresses that defeat the CPU cache. Quick sort scans contiguously and stays cache-friendly. Heap sort also does more swaps and is not stable.
Its real niche is guaranteed worst-case behaviour with constant memory — embedded and real-time systems. It also appears inside introsort (used by C++'s std::sort), which starts with quick sort and switches to heap sort if recursion gets too deep, capping the worst case.
Interactive Exploration Guide
Watch phase 1. Sifting starts from the middle of the array, never the leaves — that is why heapify is O(n).
Note when the heap is valid. Every parent now beats its children, but the array is far from sorted — a heap is only partially ordered.
Watch phase 2. Each swap sends the current maximum to its final position and the green sorted region grows leftward.
Compare the tree and the array. They are the same data — the tree is drawn from array indices, with no pointers anywhere.
Shuffle and re-run. The operation counts barely move; heap sort has no bad inputs, unlike quick sort.
Key Takeaway
Heap sort is O(n log n) in every case with O(1) extra memory — the only common sort offering both. It loses on speed to quick sort because scattered sift-down accesses wreck cache locality, and it is not stable. Use it when worst-case guarantees matter more than raw throughput.
Cheat sheet
Heap Sort
Build a max-heap, then repeatedly swap the root to the end and re-sink. Guaranteed O(n log n) with O(1) extra space — the only common sort that gets both at once.