Heap Sort: Sorting With a Binary Heap

The array is secretly a tree

Heap sort's central trick is that a plain array already is a complete binary tree if you agree on an indexing rule. For a 0-based array, the node at index i has children at 2i+1 and 2i+2, and its parent sits at (i-1)/2 (integer division). No pointers, no allocation — the tree lives entirely in the arithmetic.

A max-heap imposes one invariant on that tree: every parent is ≥ both of its children. This says nothing about left-vs-right ordering (a heap is not a sorted array), but it guarantees one thing that matters enormously — the largest element in the whole structure is always at index 0, the root. Heap sort is built entirely around exploiting that single guarantee, over and over.

Sift-down: the one operation everything is built from

The workhorse is siftDown (also called heapify or bubble-down). Given a node whose subtrees are already valid heaps but which may itself violate the invariant, it pushes that node down to its correct level by repeatedly swapping it with its larger child until it is ≥ both children (or hits a leaf).

siftDown(A, i, n):
  loop:
    l = 2i+1; r = 2i+2; big = i
    if l < n and A[l] > A[big]: big = l
    if r < n and A[r] > A[big]: big = r
    if big == i: return
    swap(A[i], A[big]); i = big

Because the path from any node to a leaf has length at most ⌊log₂ n⌋, a single siftDown costs O(log n). Critically, you must compare against the larger of the two children: swapping with the smaller one can leave a parent below its other child and silently break the heap — one of the most common bugs when writing this from memory.

The two phases of the sort

Heap sort runs in two distinct phases over the same array, entirely in place.

• Build the heap. Call siftDown on every internal node, working from the last parent up to the root: for i = n/2 - 1 down to 0: siftDown(A, i, n). Going bottom-up guarantees each node's children are already valid heaps when you process it — that's the precondition siftDown needs.
• Extract repeatedly. The root A[0] is now the maximum. Swap it with the last element, shrink the heap boundary by one (that slot is now sorted and final), and siftDown the new root over the remaining n-1 elements. Repeat until the heap has one element left.

The loop invariant of phase two is the key to correctness: at the start of each iteration, A[0..end] is a valid max-heap and A[end+1..n-1] holds the largest values, already in final sorted order. Each swap places one more element permanently and grows the sorted suffix by one; after n-1 extractions the whole array is sorted ascending.

Why it is Θ(n log n) — and why building is only Θ(n)

The extraction phase is easy to bound: n-1 iterations, each doing one siftDown costing O(log n), giving Θ(n log n). This holds in the best, average, and worst case alike — heap sort has no lucky inputs and no adversarial ones, which is precisely what makes it valuable as a worst-case guarantee.

The build phase surprises people. A naive count says n/2 nodes × O(log n) = O(n log n), but that is loose. Nodes near the bottom vastly outnumber those near the top, and they sift down only a short distance. Summing the real work, ∑ (nodes at height h) × h = ∑ (n/2ʰ⁺¹) × h, converges to a constant times n. So building the heap is Θ(n), not Θ(n log n). It's the extraction loop, not the build, that dominates the total.

Space is O(1): everything happens by swapping inside the input array, and the canonical iterative siftDown uses no recursion stack. That in-place, no-recursion property is heap sort's signature advantage over merge sort (Θ(n) auxiliary) and quicksort (O(log n) stack that can degrade to O(n)).

A tiny worked example

Sort [3, 1, 4, 1, 5]. Build-heap (bottom-up sift-downs) rearranges it into a valid max-heap, e.g. [5, 3, 4, 1, 1] — note the root is the maximum, and no ordering is promised among siblings.

• Swap root 5 with the last slot → [1, 3, 4, 1, | 5]; sift the new root down over the first 4 → [4, 3, 1, 1, | 5].
• Swap 4 to the boundary → [1, 3, 1, | 4, 5]; sift → [3, 1, 1, | 4, 5].
• Swap 3 → [1, 1, | 3, 4, 5]; sift → [1, 1, | 3, 4, 5].
• Swap 1 → [1, | 1, 3, 4, 5]. Done: [1, 1, 3, 4, 5].

Watch how the sorted suffix (after the bar) grows by exactly one element per extraction while the heap region shrinks — that's the invariant made visible.

Trade-offs: when to reach for heap sort

Heap sort's real-world reputation is rock-solid but rarely fastest. It shares quicksort's Θ(n log n) average, but its memory access pattern is far worse: siftDown jumps between indices i, 2i+1, 4i+3… scattering across the array and thrashing the CPU cache, whereas quicksort's partitioning is a linear, prefetch-friendly scan. In practice, well-tuned quicksort routinely runs 2–3× faster than heap sort on random data despite identical asymptotics.

So why use it? Two reasons. First, the worst-case guarantee: quicksort can be forced into Θ(n²) by adversarial input, heap sort never can — this is why introsort (the sort behind C++ std::sort and many standard libraries) runs quicksort but falls back to heap sort once recursion depth exceeds ~2·log₂ n, capping the worst case at Θ(n log n). Second, the O(1) space when memory is tight and recursion is undesirable. If you need stability, though, reach for merge sort instead — heap sort's long-distance swaps destroy the relative order of equal keys.

Heap sort vs the other classic comparison sorts

Algorithm	Worst time	Average time	Extra space	Stable
Heap sort	Θ(n log n)	Θ(n log n)	O(1)	No
Quicksort	Θ(n²)	Θ(n log n)	O(log n) stack	No
Merge sort	Θ(n log n)	Θ(n log n)	Θ(n)	Yes
Insertion sort	Θ(n²)	Θ(n²)	O(1)	Yes