Before the details
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).
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.
Selection sort with a better data structure
Heap sort has a clean derivation: selection sort repeatedly finds the largest remaining element, and finding it by scanning is O(n). A heap finds it in O(log n).
Same algorithm, better structure, and the complexity drops from O(n²) to O(n log n).
Two phases:
Build a max-heap from the array, in place, in O(n). Repeatedly swap the root (the maximum) with the last unsorted element, shrink the heap by one, and sift the new root down.
def heap_sort(arr):
n = len(arr)
for i in range(n // 2 - 1, -1, -1): # build the heap: O(n)
sift_down(arr, i, n)
for end in range(n - 1, 0, -1): # extract: n times O(log n)
arr[0], arr[end] = arr[end], arr[0] # max to its final position
sift_down(arr, 0, end) # restore the heap, excluding the tail
return arr
def sift_down(arr, i, size):
while True:
largest, left, right = i, 2*i + 1, 2*i + 2
if left < size and arr[left] > arr[largest]:
largest = left
if right < size and arr[right] > arr[largest]:
largest = right
if largest == i:
return
arr[i], arr[largest] = arr[largest], arr[i]
i = largest
Note that everything happens in the original array: the heap occupies the front, the sorted region grows from the back, and no auxiliary storage is needed.
Building the heap is O(n), not O(n log n)
A detail that surprises people and is worth understanding.
Sifting down from the middle backwards looks like n/2 operations each costing O(log n), suggesting O(n log n). The actual bound is O(n), because most nodes are near the bottom and have almost no distance to sift.
Half the nodes are leaves and need no work. A quarter are one level up and sift at most once. An eighth sift at most twice. Summing that series gives O(n).
Building by repeated insertion instead is O(n log n) — each insertion sifts up from a leaf, and the last insertions travel the full height. So the direction matters: sift down from the middle, not up from insertions.
Its position among the O(n log n) sorts
| | Heap sort | Quick sort | Merge sort |
|---|
| Worst case | O(n log n) | O(n²) | O(n log n) |
| Extra space | O(1) | O(log n) stack | O(n) |
| Stable | No | No | Yes |
| Cache behaviour | Poor | Excellent | Good |
| Typical speed | Slowest of the three | Fastest | Middle |
Heap sort is the only one with both a guaranteed O(n log n) and O(1) extra space. That combination is unique among the classical sorts, and it is why the algorithm survives.
It is also the slowest of the three in practice, and the reason is cache behaviour: sifting jumps between indices i, 2i+1 and 2i+2, which on a large array means touching memory pages far apart. Quick sort's partitioning scans sequentially, which modern CPUs handle far better.
So heap sort is rarely chosen on its own — and it is chosen as a fallback, which is a genuinely important role.
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.
Where that leaves you
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.
Introsort: where heap sort actually runs
C++'s std::sort is introsort, and heap sort is its safety net.
The algorithm starts with quick sort. It tracks recursion depth, and if the depth exceeds roughly 2 log n — evidence that pivots are being chosen badly and the O(n²) case is developing — it switches to heap sort for that subarray. Below a small threshold it finishes with insertion sort.
The result combines all three strengths:
| Component | Provides |
|---|
| Quick sort | Speed in the common case |
| Heap sort | The O(n log n) worst-case guarantee |
| Insertion sort | Low overhead on small subarrays |
That is heap sort's real production role: it is never the fastest choice, and it is the one that makes quick sort's worst case impossible. Without it, std::sort would have no guarantee.
Python takes a different route — Timsort, which is a stable merge sort — because Python guarantees stability and heap sort is not stable.
Why it is not stable
Sifting swaps elements that are far apart in the array, so equal elements can be reordered relative to their original positions.
Sorting [3a, 3b, 1] as a max-heap: 3a becomes the root, is swapped with the last element, and 3b ends up before it. The two equal values have exchanged order.
Making it stable requires attaching original indices as a tiebreaker, which needs O(n) extra space — and that removes the in-place advantage that was the reason to choose heap sort.
So heap sort's guarantee is worst-case time and constant space, never stability. When stability matters, merge sort or Timsort is the answer.
The heap itself is far more widely used than heap sort:
Priority queues in Dijkstra's algorithm, A*, and any scheduler.
Top-k selection. A min-heap of size k gives the k largest of n items in O(n log k) time and O(k) space — better than sorting everything when k is small. This is what heapq.nlargest does.
Partial sorting. Stopping heap sort after k extractions gives the k largest elements in sorted order, in O(n + k log n).
k-way merging. A heap of the front elements of k sorted streams merges them efficiently, which is how external sorting combines runs.
Running medians. Two heaps — a max-heap of the lower half and a min-heap of the upper — give the median of a stream in O(log n) per element.
Why building the heap is O(n), not O(n log n)
The claim that heapify costs O(n) looks wrong -- there are n elements and each sift is O(log n) -- and it is the one part of heap sort worth checking rather than accepting. Count the sift steps and the answer falls out of the shape of the tree.
Questions people ask
Why is heap sort slower than quick sort if both are O(n log n)? Cache behaviour. Sifting jumps between distant indices; quick sort scans sequentially.
Is it stable? No, and making it stable requires extra space, which defeats its purpose.
Why is building the heap O(n)? Most nodes are near the leaves and sift a short distance; the series sums to O(n).
Where is it used in practice? As introsort's fallback, providing the worst-case guarantee behind quick sort's speed.
Max-heap or min-heap for ascending order? Max-heap — the largest goes to the end of the array first.
Can it sort in place? Yes, and that is its distinguishing feature: O(1) extra space with a guaranteed O(n log n).
Recap in one screen
- Build a max-heap in O(n), then repeatedly swap the root to the end and sift down.
- Building by sifting down from the middle is O(n); building by repeated insertion is O(n log n).
- Uniquely among classical sorts: guaranteed O(n log n) and O(1) extra space.
- Slower than quick sort in practice because sifting has poor cache locality, and not stable.
- Its production role is introsort's fallback, which is what gives
std::sort its worst-case guarantee.