Heap Sort

Heap sort turns the array into a max-heap — a binary tree where every parent is at least as big as its children — and then repeatedly rips the maximum off the top and parks it at the end. It sorts in place, needs no extra array, and runs in guaranteed O(n log n) time.

The one primitive you need is sift-down: given a node that may be smaller than its children, swap it with its larger child and keep going until it lands somewhere it dominates.

Intuition

A max-heap is the perfect tool for "give me the biggest thing left" on demand. The root is always the maximum, and after you remove it you can restore the heap in O(log n) instead of re-scanning everything.

So heap sort has two phases. Build the heap once: starting from the last parent and walking back to the root, sift each node down so the whole array obeys the heap rule. Extract repeatedly: the root is the current maximum, so swap it to the last open slot — that slot is now permanently correct — then pretend the heap is one smaller and sift the new root down to repair it. Each extraction locks one more value into its final place, filling the array from the right toward the left.

Walk through it

Step through the animation on the right. The cells are the flat array [4, 10, 3, 5, 1]; the i pointer marks the node being sifted and the child pointer marks its larger child.

Build phase. The last parent is index 1 (value 10). Its children 5 and 1 are both smaller, so it already obeys the rule and nothing moves. Next is the root, index 0 (value 4): its larger child is 10, so 4 and 10 swap. The 4 slides down to index 1, then sifts again against its new children 5 and 1 — 5 is bigger, so they swap once more. The array is now the max-heap [10, 5, 3, 4, 1].

Extract phase. Swap the root 10 with the last cell; 10 is now sorted at index 4. Sift the new root 1 down, and 5 bubbles up. Repeat: 5 settles at index 3, then 4 at index 2, then 3 at index 1, and finally 1 is alone at index 0. Every cell turns sorted and the array reads [1, 3, 4, 5, 10].

The code, line by line

def heapify(a, n, i):
    largest = i
    l, r = 2 * i + 1, 2 * i + 2
    if l < n and a[l] > a[largest]:
        largest = l
    if r < n and a[r] > a[largest]:
        largest = r
    if largest != i:
        a[i], a[largest] = a[largest], a[i]
        heapify(a, n, largest)
 
def heap_sort(a):
    n = len(a)
    for i in range(n // 2 - 1, -1, -1):
        heapify(a, n, i)
    for end in range(n - 1, 0, -1):
        a[0], a[end] = a[end], a[0]
        heapify(a, end, 0)

• heapify(a, n, i) is the sift-down: it assumes i's subtrees are already heaps and pushes i down until the rule holds. n is the current heap size, so it can ignore the sorted tail.
• Lines 4–7 find largest among the node and its two children. The l < n / r < n guards skip children that fall outside the live heap.
• Lines 8–10 are the move: if a child won, swap it up and recurse on the spot the value fell into. If largest is still i, the node is already in place and we stop.
• Line 14 builds the heap by sifting every parent — indices n // 2 - 1 down to 0. Leaves (the back half) are trivially heaps, so we skip them.
• Lines 16–17 are the extraction loop: swap the max at the root to position end, then heapify(a, end, 0) repairs the heap over the shrinking prefix [0, end), leaving the sorted suffix untouched.

Complexity

Heap sort is O(n log n) in the best, average, and worst case — there is no pathological input that degrades it, unlike quicksort's O(n²). It sorts in place with only O(1) extra memory (the recursion can be rewritten as a loop). The catch is that it is not stable and its scattered parent-child accesses are cache-unfriendly, so a well-tuned quicksort usually beats it in wall-clock time.

When to use / pitfalls

Practice