Heap Sort

Heap sort is a comparison-based sorting algorithm that uses a binary max-heap as its engine. It builds a max-heap from the input array in O(n) time, then repeatedly extracts the maximum (the root) and places it at the end of the array, shrinking the heap by one each time. The result is a sorted array in O(n log n) worst-case time — strictly better than Quicksort’s O(n²) worst — using only O(1) extra space (truly in-place). The price paid for these guarantees is a poor cache profile (heap operations jump around the array via the 2i+1 / 2i+2 index arithmetic) and the loss of stability. Heap sort is rarely the primary sort in modern standard libraries, but it is the fallback half of Intro Sort (used by C++ std::sort and the .NET runtime), guarding against quicksort’s pathological inputs.

1. Intuition — Repeatedly Drafting the Tallest Player

Imagine a gym full of basketball players you want sorted by height, tallest at the back of a single-file line.

• First, organize all the players into a bracket in which every “parent” player is taller than the two “child” players underneath them. This is the max-heap property. The single tallest player in the whole gym ends up at the top of the bracket.
• Pull the tallest player out and walk them to the back of the line. Their final position is locked.
• A hole opens at the top of the bracket. Take whoever is currently at the very bottom of the bracket (the “scrub” position), put them at the top, and let them sift down — at each step, swap with whichever of their two children is taller. Eventually they settle at a level where the heap property holds again. Now a new (second-tallest) player is at the top.
• Repeat: extract the new tallest, walk them to the second-to-last line position, refill the hole from the bottom, sift down. Continue until the bracket is empty.

That is exactly heap sort. The “bracket” is a max-heap stored as an array; “walk to the back of the line” is a swap with the array’s last unsorted slot; “sift down” restores the heap property after each extraction.

The big insight is that the same array stores both the heap (at the front) and the sorted output (at the back), with a moving boundary between the two regions. No auxiliary buffer is ever needed — that’s where the O(1) space comes from.

2. Tiny Worked Example (n = 6)

Sort [3, 1, 6, 5, 2, 4] in ascending order using a max-heap.

Phase 1 — Build a max-heap (Floyd’s bottom-up heapify)

We start at the last non-leaf node (index n//2 - 1 = 2, holding 6) and call sift_down on each index walking back to 0. The leaves (indices 3, 4, 5) are trivially heaps of size 1.

Initial array (as a complete tree):
                3 (i=0)
              /        \
           1 (i=1)     6 (i=2)
          /     \      /
        5 (i=3) 2 (i=4) 4 (i=5)

• i = 2, value 6: children are 4 only (2*2+2 = 6 is out of bounds). 6 > 4, heap property already holds. No swap.
• i = 1, value 1: children are 5 (left) and 2 (right). Larger child is 5. 1 < 5, swap. Array becomes [3, 5, 6, 1, 2, 4]. Now sift the displaced 1 further: its new position is i=3, which is a leaf. Stop.
• i = 0, value 3: children are 5 (left) and 6 (right). Larger child is 6. 3 < 6, swap. Array becomes [6, 5, 3, 1, 2, 4]. Now sift the displaced 3 further at i=2: child is 4. 3 < 4, swap. Array becomes [6, 5, 4, 1, 2, 3]. 3 is now at i=5 (leaf). Stop.

Heap built: [6, 5, 4, 1, 2, 3]. Verify: arr[0]=6 is max, every parent ≥ children.

Phase 2 — Repeated extract-max + sift-down

Maintain a heap_end pointer (initially n - 1 = 5) marking the last index still part of the heap. Everything strictly to the right of heap_end is the sorted suffix.

Step	Action	Array state	Sorted suffix
1	Swap arr[0] ↔ arr[5]; shrink heap to size 5; sift down 3 from root	`[5, 3, 4, 1, 2,	6]→ sift →[5, 3, 4, 1, 2,
2	Swap arr[0] ↔ arr[4]; shrink to size 4; sift down 2 from root	`[2, 3, 4, 1,	5, 6]→ sift →[4, 3, 2, 1,
3	Swap arr[0] ↔ arr[3]; shrink to size 3; sift down 1 from root	`[1, 3, 2,	4, 5, 6]→ sift →[3, 1, 2,
4	Swap arr[0] ↔ arr[2]; shrink to size 2; sift down 2 from root	`[2, 1,	3, 4, 5, 6]→ sift →[2, 1,
5	Swap arr[0] ↔ arr[1]; shrink to size 1; sift down 1 from root	`[1,	2, 3, 4, 5, 6]→ sift →[1,
6	Heap of size 1 is trivially “sorted”; stop	[1, 2, 3, 4, 5, 6]	[1, 2, 3, 4, 5, 6]

Final: [1, 2, 3, 4, 5, 6]. Sorted, in place, no scratch buffer.

Notice how the array’s front shrinks as a heap and its back grows as the sorted suffix — the two regions never overlap.

3. Pseudocode

heap_sort(arr):
    n := length(arr)
    build_max_heap(arr)                          # O(n)
    for end := n - 1 down to 1:
        swap arr[0], arr[end]                    # extract max → final position
        sift_down(arr, 0, end)                   # restore heap on prefix [0..end-1]

build_max_heap(arr):
    n := length(arr)
    for i := (n // 2) - 1 down to 0:             # last non-leaf back to root
        sift_down(arr, i, n)                     # Floyd's O(n) heapify

sift_down(arr, i, heap_size):
    while true:
        l := 2*i + 1
        r := 2*i + 2
        largest := i
        if l < heap_size and arr[l] > arr[largest]:
            largest := l
        if r < heap_size and arr[r] > arr[largest]:
            largest := r
        if largest == i:
            return                               # heap property holds, done
        swap arr[i], arr[largest]
        i := largest                             # follow the swap downward

The heap_size parameter to sift_down is what implements the “shrinking heap” — we never look beyond heap_size, so the sorted suffix is invisible to the heap operations.

4. Python Implementation

def heap_sort(arr: list[int]) -> None:
    """Sort `arr` in place, ascending, using an in-place max-heap."""
    n = len(arr)
    # Phase 1: build max-heap in O(n) (Floyd's bottom-up heapify)
    for i in range(n // 2 - 1, -1, -1):
        _sift_down(arr, i, n)
    # Phase 2: repeatedly extract the max
    for end in range(n - 1, 0, -1):
        arr[0], arr[end] = arr[end], arr[0]      # max → final position
        _sift_down(arr, 0, end)                  # heap shrinks: end is now the new size
 
def _sift_down(arr: list[int], i: int, heap_size: int) -> None:
    while True:
        l, r = 2 * i + 1, 2 * i + 2
        largest = i
        if l < heap_size and arr[l] > arr[largest]:
            largest = l
        if r < heap_size and arr[r] > arr[largest]:
            largest = r
        if largest == i:
            return
        arr[i], arr[largest] = arr[largest], arr[i]
        i = largest

Notes on the implementation:

• The outer for end in range(n - 1, 0, -1) shrinks the active heap by one each iteration. We don’t need end == 0 because a heap of size 1 is already sorted.
• Python’s standard library has a heap module — import heapq — but it’s a min-heap with no in-place “max-heap sort” wrapper. Building a max-heap with heapq requires negating values, which is ugly; for a real heap-sort demonstration the hand-rolled version above is cleaner and more honest about the algorithm.
• For descending order, replace > with < in _sift_down (turning it into a min-heap), then the same outer loop produces descending output.

5. Complexity

5.1 Time

Phase 1 (build_max_heap) is O(n), not O(n log n). This is the surprising bit. Naively, calling sift_down on n/2 nodes, each costing O(log n), suggests O(n log n). But that overcounts: most nodes are near the bottom of the tree, where sift_down is short. A node at height h (counting up from the leaves) costs O(h) to sift, and there are at most ⌈n / 2^(h+1)⌉ nodes at height h. Summing:

Total work = Σ_{h=0}^{log n}  ⌈n / 2^(h+1)⌉ · O(h)
           = O(n) · Σ_{h=0}^{∞} h / 2^h
           = O(n) · 2                            (the series Σ h/2^h converges to 2)
           = O(n)

where each symbol means: h is the height in the heap (leaves at h=0); 2^(h+1) is the worst-case spacing between nodes at that height in the array; the series Σ h/2^h is a known convergent geometric-like sum equal to 2 (CLRS Eq. A.8). So heapification is linear, not log-linear.

Phase 2 (n-1 extractions) is O(n log n). Each extraction does one swap (O(1)) plus one sift_down from the root, costing O(log k) where k is the current heap size. Total: Σ_{k=2}^{n} log k = log(n!) = Θ(n log n) by Stirling’s approximation (log(n!) ≈ n log n - n).

Total time: O(n) + O(n log n) = O(n log n) in worst, average, and best case. Heap sort has no input-dependent shortcuts — even an already-sorted array goes through the same n log n operations. This is occasionally noted as a downside relative to adaptive sorts like Tim Sort which achieve O(n) on already-sorted data.

5.2 Comparison with the Comparison-Sort Lower Bound

Any comparison-based sort must do Ω(n log n) comparisons in the worst case. The argument: the algorithm’s run can be modeled as a decision tree where each internal node is a comparison and each leaf is a permutation of the input. There are n! leaves (one per possible input ordering), so the tree’s height (longest path = worst-case comparison count) is at least log₂(n!) = Θ(n log n) (Stirling). Heap sort matches this lower bound exactly — it is asymptotically optimal among comparison sorts.

5.3 Space

• Auxiliary space: O(1) — the heap lives inside the input array; the only extra storage is a constant number of indices and temporary variables for swaps.
• Recursion depth: O(1) if sift_down is iterative (as above). Recursive sift_down would use O(log n) stack — small but non-zero.

This O(1) auxiliary is heap sort’s main selling point over Merge Sort (O(n) aux).

6. Stability — Heap Sort Is Not Stable

Heap sort is not stable: equal elements may be reordered relative to their input positions. The instability comes from sift_down: when two equal elements occupy parent and child positions in the heap, the swap during sifting can move one past the other, and once they are at different positions in the array there is no record of which was “earlier originally.”

Concrete example: input [(2, 'a'), (2, 'b'), (1, 'c')] sorted on the integer key.

• Build max-heap: [(2, 'a'), (2, 'b'), (1, 'c')] is already a max-heap (parent 2 ≥ children 2 and 1).
• Extract max: swap index 0 with index 2 → [(1, 'c'), (2, 'b'), | (2, 'a')]. Sift (1, 'c') down: child (2, 'b') is larger, swap → [(2, 'b'), (1, 'c'), | (2, 'a')].
• Extract max: swap index 0 with index 1 → [(1, 'c'), | (2, 'b'), (2, 'a')].
• Done: [(1, 'c'), (2, 'b'), (2, 'a')].

The original input had (2, 'a') before (2, 'b'). The output reverses them. Stability lost.

A stable heap sort can be constructed by augmenting each key with its original index (key, original_index) and breaking ties on the index, but this requires O(n) extra storage and defeats the in-place advantage.

7. Cache Behavior — Heap Sort’s Big Practical Weakness

In the asymptotic complexity analysis, heap sort and Quicksort are both O(n log n). In practice, on modern hardware, quicksort beats heap sort by a factor of 2–3× on random data of substantial size. The reason is the memory access pattern.

A modern CPU loads memory in cache lines of 64 bytes. If your algorithm accesses memory locations near each other in time-near-each-other, the second access hits in cache (nanoseconds). If it jumps around, the second access misses cache and goes to main memory (~100 ns, a 100× slowdown).

• Quicksort’s partition walks the array linearly with two pointers. Every access is to the next or previous slot. Cache lines stream in perfectly.
• Heap sort’s sift_down at index i accesses index 2i + 1 and 2i + 2. For a heap of size 1 million, sifting the root jumps to indices ~2, ~5, ~11, ~22, ~45, … — each access is in a different cache line. The CPU spends most of its time waiting for memory.

LaMarca and Ladner measured this empirically in two companion studies — “The Influence of Caches on the Performance of Heaps” (ACM Journal of Experimental Algorithmics, vol. 1, article 4, 1996) and the broader “The Influence of Caches on the Performance of Sorting” (SODA 1997; the journal version appeared in Journal of Algorithms 31(1):66–104, 1999). They proposed cache-conscious heap layouts (e.g., aligning a node’s children to share a cache line, and increasing the heap’s fan-out) to mitigate the problem. In practice, no widely-deployed standard library uses binary heap sort as the primary sort, precisely because of this cache inefficiency — though, as §8.2 notes, the smoothsort variant is a production primary sort in musl libc’s qsort.

8. Variants and Where Heap Sort Lives in Production

8.1 Intro Sort (the practical use)

Musser (1997) “Introspective Sorting and Selection Algorithms” (Software: Practice and Experience 27:983–993) introduced Intro Sort: start with quicksort; track recursion depth; if depth exceeds 2 ⌊log₂ n⌋, switch the misbehaving subproblem to heap sort. This gives quicksort’s average-case speed with heap sort’s worst-case O(n log n) guarantee.

Intro sort is what C++ std::sort uses (libstdc++, libc++, MSVC STL), as well as the .NET runtime’s Array.Sort and Rust’s slice::sort_unstable. So heap sort, while rarely the front-line algorithm, is in the bloodstream of essentially every modern systems language’s standard library — its job is to catch the pathological inputs that would make quicksort go quadratic.

8.2 Smooth Sort (Dijkstra)

Dijkstra (1981, EWD 796a) proposed smooth sort, a heap-sort variant that replaces the single binary heap with a Leonardo heap — a forest of trees whose sizes are consecutive Leonardo numbers (L(0)=1, L(1)=1, L(2)=3, L(3)=5, L(4)=9, L(5)=15, L(6)=25, ..., defined by L(k) = L(k-1) + L(k-2) + 1, a Fibonacci-like recurrence). On already-sorted input it runs in O(n); on random input it stays O(n log n), and its auxiliary space is O(1) (the forest structure is encoded in a small bit-vector of which Leonardo sizes are present, not in pointers). It is adaptive — it degrades smoothly from linear to log-linear as the input becomes more disordered, which is the source of the name.

Smooth sort is genuinely used in production: the musl C library implements its qsort with smoothsort, describing it in-source as “Smoothsort, an adaptive variant of Heapsort. Memory usage: O(1). Run time: Worst case O(n log n), close to O(n) in the mostly-sorted case” (musl src/stdlib/qsort.c). It is far less common than introsort-based sorts, however, because the Leonardo-heap bookkeeping is intricate and error-prone (the implicit forest is navigated by index arithmetic over a bit-vector, with no explicit pointers), so most other standard libraries avoid it.

8.3 Weak-Heap Sort

Uses a “weak heap” (a relaxed heap variant, Edelkamp & Stiegeler 2002) doing fewer comparisons than classical heap sort — close to the information-theoretic lower bound of n log₂ n - 1.4427n + O(log n). Useful when comparison cost dominates (e.g., comparing long strings). Rarely worth it when comparisons are cheap.

8.4 d-ary Heap Sort

Use a d-ary heap (each node has d children) instead of binary. sift_down does d-1 comparisons per level but the tree height drops to log_d n. For some d (typically 4 or 8), this can be faster on hardware where comparisons are cheap and the smaller height improves cache behavior. The heapq module in Python is binary; some database engines use 4-ary.

9. When To Use Heap Sort

9.1 Use heap sort when

• You need a worst-case O(n log n) guarantee and cannot use Merge Sort because of memory constraints (heap sort is O(1) aux; merge sort is O(n)).
• You’re in a real-time or embedded environment where worst-case bounds matter more than average-case speed (medical devices, avionics, vehicle ECUs).
• You want introsort behavior — start with Quicksort, fall back to heap sort if recursion depth blows up. (You probably don’t write this yourself; you call std::sort and rely on its implementation.)
• You only need the top-k elements rather than a full sort: build a min-heap of size k, push every element, pop if size exceeds k. Final heap is the top-k. O(n log k). (Conceptually heap-sort-like; see Binary Heap for top-k pattern.)

9.2 Don’t use heap sort when

• You need stability — use Merge Sort or Tim Sort.
• You’re sorting random data and care about wall-clock speed — use Quicksort or Intro Sort instead; the cache penalty makes raw heap sort slower.
• Data is mostly sorted — heap sort makes no use of presortedness; Tim Sort gets O(n) on this input.
• You’re sorting a linked list — heap sort needs random access; use merge sort.

10. Pitfalls

10.1 Confusing “Build” Order (Top-Down vs Bottom-Up)

The naive way to build a heap is to start with an empty heap and insert each element one at a time. That is O(n log n). Floyd’s bottom-up heapify (start at the last non-leaf, sift down each node going up to the root) is O(n). The two are not interchangeable in complexity. Use bottom-up heapify for the build phase.

10.2 Forgetting to Shrink the Heap

After swapping the max into its final position, the new heap size is one less than before. Calling sift_down(arr, 0, n) instead of sift_down(arr, 0, end) would re-include the just-placed element as part of the heap, corrupting the sorted suffix. Always pass the current heap size to sift_down.

10.3 Min-Heap vs Max-Heap Confusion

For ascending sort, you want a max-heap (extract-max repeatedly puts the biggest element at the back). For descending sort, you want a min-heap. Picking the wrong polarity gives a perfectly correct sort in the opposite direction — embarrassing in an interview.

10.4 Using Recursion in sift_down

Recursive sift_down is cleaner-looking but adds O(log n) to the call stack and prevents tail-call optimization (Python doesn’t optimize tail calls anyway). Iterative sift_down, as shown above, is preferred.

10.5 Off-by-One on the Last Non-Leaf

For a 0-indexed heap of size n, the last non-leaf is index n // 2 - 1, not n // 2. The leaves are at indices n // 2 .. n - 1. Getting this wrong by one wastes a tiny amount of work but is occasionally the source of confusion in code review.

10.6 Assuming It’s Stable Because It’s Sorting

Heap sort is not stable. If your sort is part of a multi-key sort pipeline (sort by secondary key first, then primary, expecting stability to preserve secondary order within equal-primary groups), heap sort will silently break the pipeline. Use Merge Sort or Tim Sort.

11. Diagram — The Two-Region Invariant

flowchart TD
    subgraph Init["Initial state (n=6)"]
        A1["Array: [3, 1, 6, 5, 2, 4]<br/>Heap region: indices 0..5<br/>Sorted region: empty"]
    end
    subgraph Built["After build_max_heap"]
        A2["Array: [6, 5, 4, 1, 2, 3]<br/>Heap: 0..5 (root=6 is max)<br/>Sorted: empty"]
    end
    subgraph Iter1["After 1st extract"]
        A3["Array: [5, 3, 4, 1, 2 | 6]<br/>Heap: 0..4<br/>Sorted: [6]"]
    end
    subgraph Iter2["After 2nd extract"]
        A4["Array: [4, 3, 2, 1 | 5, 6]<br/>Heap: 0..3<br/>Sorted: [5, 6]"]
    end
    subgraph End["Final"]
        A5["Array: [1, 2, 3, 4, 5, 6]<br/>Heap: empty<br/>Sorted: 0..5"]
    end
    Init --> Built --> Iter1 --> Iter2 -->|...| End

What this diagram shows. Heap sort’s central invariant: the array is always partitioned into a prefix that is a valid max-heap and a suffix that is the final sorted output. The boundary between them moves leftward by one slot per outer-loop iteration. The two regions never overlap, so no auxiliary buffer is needed — that is exactly why heap sort is O(1) extra space. When the heap region shrinks to size 0 (or 1 — a singleton heap is trivially a heap), the suffix is the whole array, sorted.

12. Comparison with Merge Sort and Quicksort

Property	Heap Sort	Merge Sort	Quicksort
Worst-case time	O(n log n)	O(n log n)	O(n²)
Average-case time	O(n log n)	O(n log n)	O(n log n), small constant
Best-case time	O(n log n)	O(n log n)	O(n log n)
Adaptive (faster on sorted)?	❌	❌	❌
Stable?	❌	✅	❌
In-place (O(1) aux)?	✅	❌ (O(n) aux)	✅ (O(log n) stack)
Cache behavior	Poor (heap jumps)	Good (sequential merges)	Excellent (sequential partition)
Recursion depth	O(1) iterative / O(log n) recursive	O(log n)	O(log n) avg / O(n) worst
Used as primary sort by	Few (real-time embedded)	Java Object[] Arrays.sort (legacy)	Most stdlibs (via Intro Sort)
Used as fallback by	Intro Sort (C++ std::sort, .NET, Rust unstable sort)	Tim Sort (Python, Java for objects)	—

The takeaway: heap sort wins on worst-case guarantee + in-place memory but loses on constants + cache. Quicksort wins on average-case constants + cache but has a quadratic worst case. Merge sort wins on stability + worst-case guarantee but uses extra memory. The production sweet spot, Intro Sort, deliberately combines quicksort and heap sort to get average-case quicksort speed plus heap sort’s worst-case guarantee.

13. Common Interview Problems

Problem	Heap Sort Connection
”Sort an array, in place, with O(1) extra memory”	Heap sort is the standard answer (alternatives: in-place merge sort, but that’s exotic).
”Find the k-th largest element in an unsorted array”	Quickselect is O(n) average but heap-of-size-k is O(n log k) and uses the same heap operations.
”Sort k sorted lists” (LC 23)	k-way merge with a min-heap — uses heap operations, conceptually heap-sort-flavored.
”Implement a priority queue”	Same data structure (binary heap); heap sort is just “extract-max in a loop” applied to that PQ.
”Why does C++ std::sort give O(n log n) worst case when quicksort is O(n²) worst?”	Because it’s Intro Sort, which falls back to heap sort when quicksort recursion gets too deep.

14. Open Questions

• Is there a measurable cache-conscious heap layout (e.g., the LaMarca-Ladner “B-heap”) that closes the heap-sort vs quicksort wall-clock gap on modern CPUs? Worth implementing and benchmarking on contemporary hardware.
• What is the exact recursion-depth threshold most production introsort implementations use? CLRS suggests 2 log₂ n; some implementations use 2 (log₂ n) + small constant.
• How does heap sort perform when keys are very large (long strings, structs)? The comparison cost may dominate the cache-miss cost, narrowing the gap with quicksort.

15. See Also

• Binary Heap — the underlying data structure; sift_down and bottom-up build are defined there in detail
• Merge Sort — guaranteed O(n log n) and stable, but O(n) aux
• Quicksort — fastest average case, but O(n²) worst
• Intro Sort — production hybrid that uses heap sort as a fallback
• Tim Sort — Python/Java’s adaptive merge-sort hybrid (preferred when stability matters)
• Insertion Sort — used as the small-array base case alongside heap sort in many hybrids
• Quickselect — quicksort’s selection variant; heap-of-size-k is the heap-sort analog for top-k
• Big-O Notation
• Master Theorem
• SWE Interview Preparation MOC