Sorting7 min read

Heap Sort

A tournament bracket where the champion always rises to the top
time (all cases):\(O(n \log n)\)space:\(O(1)\) in-placestable:Nobuild heap:\(O(n)\)

Imagine a tournament bracket where every match is played simultaneously at every round. The rule: the winner of each match must be stronger than both their children. At the end of any round, the very top of the bracket holds the strongest player. Pull them out, collapse the bracket, and run it again — the next strongest rises. That's heap sort.

More precisely: it uses a max-heap — a binary tree where every parent is larger than its children. The array representation stores it compactly: children of index i live at 2i+1 and 2i+2; parent of i is at ⌊(i−1)/2⌋. No pointers needed.

Phase 1: Build the Heap in \(O(n)\)

You might think inserting n elements one by one into a heap costs \(O(n \log n)\). But there's a smarter way: Floyd's heapify. Start from the last non-leaf node (index ⌊n/2⌋−1) and work backwards, sifting each node down to its correct position. Leaves do zero work; nodes near the bottom do very little. The work sums to a geometric series that converges to \(O(n)\) — a surprising fact that's proven by summing h·n/2^h over all heights h.

Phase 2: Sort by Repeated Extract-Max

Now the largest element sits at the root (index 0). Swap it with the last element in the heap, shrink the heap by one, and sift the new root down to restore the heap property. The extracted element is now in its correct sorted position at the end of the array. Repeat n−1 times. Each sift-down costs \(O(\log n)\), and we do n of them: \(O(n \log n)\) total.

The sort happens entirely in-place. The heap lives in the front of the array; the sorted portion grows from the back. No extra buffer needed.

Why Heap Sort Loses in Practice

Despite its beautiful properties — \(O(n \log n)\) guaranteed, \(O(1)\) space, no bad inputs — heap sort is slower than quicksort in practice. The culprit: cache unfriendliness. Sift-down jumps between parent (index i) and child (index 2i+1), which are far apart in large arrays. This pattern causes many CPU cache misses, making heap sort 2–5× slower than quicksort empirically.

Merge sort accesses memory sequentially (cache-friendly). Quicksort partitions contiguous ranges (cache-friendly). Heap sort bounces around — not cache-friendly. Its niche is as the safety net in Introsort: when quicksort detects it's degenerating (recursion depth > 2 log n), it falls back to heap sort for the \(O(n \log n)\) guarantee without extra memory.

Note: Floyd's heapify is a sneaky \(O(n)\) trick: it starts at the bottom of the tree, where most nodes live and almost no work is needed. Only the topmost nodes (few of them) do real work. The math: Σ h·(n/2^h) = \(O(n)\). Building a heap is linear!

Heap Sort Implementation

def heapify(arr, n, i):
    """Sift arr[i] down within heap of size n."""
    largest = i
    left, right = 2*i + 1, 2*i + 2
    if left < n and arr[left] > arr[largest]:
        largest = left
    if right < n and arr[right] > arr[largest]:
        largest = right
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)


def heap_sort(arr):
    n = len(arr)
    # Phase 1: Build max-heap in O(n)
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    # Phase 2: Extract max n-1 times
    for end in range(n - 1, 0, -1):
        arr[0], arr[end] = arr[end], arr[0]   # move max to sorted section
        heapify(arr, end, 0)                   # restore heap in remaining part
    return arr


data = [12, 11, 13, 5, 6, 7]
print(heap_sort(data))
Output
[5, 6, 7, 11, 12, 13]

Complexity

🏗️ Build max-heap (Floyd's)Heapify bottom-up; geometric series sums to \(O(n)\)
Linear — surprisingly fast\(O(n)\)
📤 Extract-max (sift down)Root swaps to end, then sifts down to restore heap
Logarithmic per extract\(O(\log n)\)
⏱️ Overall sort — all cases\(O(n)\) build + \(O(n \log n)\) extractions — best = worst = average
Linearithmic, no bad inputs\(O(n \log n)\)
💾 Auxiliary spaceSorted section grows in the same array — no extra buffer
Constant — truly in-place\(O(1)\)

Quick check

What is the time complexity of building a max-heap using Floyd's algorithm?

Continue reading

Basic Sorts
Sorting a hand of cards — three ways, one speed
→
Merge Sort
Split, sort each half, merge — guaranteed \(O(n \log n)\) every time
→