Heap Sort vs Quick Sort: What the Heap Actually Buys You

On paper, heap sort looks like the sort that should have won. It is O(n log n) in the worst case, which quick sort is not. It sorts in place, which merge sort does not. It needs no recursion and no extra array. And yet the default sort in most libraries is a quick sort variant, with heap sort kept around as a safety net.

The reason is not in the Big-O. It is in what the two algorithms do to memory, and it is worth being able to explain.

The problem it solves

You need to sort n values, and you have two requirements that usually pull against each other: a hard worst-case bound (no input, however adversarial, should make you quadratic) and no extra memory proportional to n.

Merge sort gives the bound but needs a second array. Quick sort is in place but can degrade to O(n²) on bad pivots. Heap sort is the classic algorithm that gives both at once.

The intuition

Heap sort treats the array as a binary tree without building one: index i has children at 2i + 1 and 2i + 2. First it rearranges the array into a max-heap, where every parent is at least as large as its children, so the maximum sits at index 0. Then it repeats one move: swap the root to the end of the unsorted region — that value is now final — shrink the heap by one, and sift the new root down to restore the heap rule.

Every sift walks one root-to-leaf path, which is log n long, and there are n of them. That is the guarantee: nothing about the input can make the tree taller.

Quick sort, by contrast, bets. It picks a pivot, sweeps the range once to split it into smaller and larger, and recurses. If pivots land near the middle, the recursion is log n deep. If they land at the edges, it is n deep.

The heap buys a worst case that cannot be attacked. It pays for it with memory access that jumps all over the array.

Look at the index sequence during a sift: 0, then 1 or 2, then 3–6, then 7–14… each step roughly doubles the index. After a few levels, consecutive accesses are thousands of slots apart. Quick sort's partition does the opposite: it walks the range left to right, touching neighbours in order, which is exactly the pattern CPU caches and prefetchers are built to reward.

Watch it run

The bars are the same array throughout. First every non-leaf is sifted down until the largest value reaches the front. Then each round swaps that maximum into the sorted tail on the right and re-sifts the shorter heap. Watch the swaps inside a sift: they are never between neighbours.

The code

Both sorts run on a Probe: an array that counts comparisons and simulates a small cache, where 16 neighbouring slots share one line and the 64 most recent lines are kept. It is a toy model of a real CPU cache, but it measures the thing that matters — how often an access lands somewhere not recently touched.

import random
from collections import OrderedDict

class Probe:
    """An array that counts comparisons and misses in a tiny simulated cache."""
    def __init__(self, a, line=16, lines=64):
        self.a, self.cmp, self.miss = a, 0, 0
        self.line, self.lines, self.cache = line, lines, OrderedDict()
    def __getitem__(self, i):
        tag = i // self.line                   # 16 neighbours share one line
        if tag in self.cache:
            self.cache.move_to_end(tag)
        else:
            self.miss += 1
            self.cache[tag] = True
            if len(self.cache) > self.lines:
                self.cache.popitem(last=False)
        return self.a[i]
    def swap(self, i, j):
        self.a[i], self.a[j] = self[j], self[i]

def heap_sort(p):
    def sift(i, size):
        while 2 * i + 1 < size:
            c = 2 * i + 1                      # children live at 2i+1 and 2i+2
            if c + 1 < size:
                p.cmp += 1
                if p[c + 1] > p[c]:
                    c += 1
            p.cmp += 1
            if p[i] >= p[c]:
                return
            p.swap(i, c)
            i = c                              # the next step jumps to ~2i
    n = len(p.a)
    for i in range(n // 2 - 1, -1, -1):
        sift(i, n)
    for end in range(n - 1, 0, -1):
        p.swap(0, end)                         # the max goes to its final slot
        sift(0, end)

def quick_sort(p, lo=0, hi=None, first_pivot=False):
    hi = len(p.a) - 1 if hi is None else hi
    while lo < hi:
        p.swap(lo if first_pivot else random.randint(lo, hi), hi)
        pivot, store = p[hi], lo
        for i in range(lo, hi):                # one left-to-right scan
            p.cmp += 1
            if p[i] < pivot:
                p.swap(i, store)
                store += 1
        p.swap(store, hi)
        if store - lo < hi - store:            # recurse on the smaller side
            quick_sort(p, lo, store - 1, first_pivot)
            lo = store + 1
        else:
            quick_sort(p, store + 1, hi, first_pivot)
            hi = store - 1

Now the race, on 100,000 shuffled values, then on the inputs that break quick sort, then a correctness check against Python's sorted on thousands of small arrays full of duplicates.

random.seed(6)
n = 100_000
data = random.sample(range(n), n)
for name, sort in (("heap", heap_sort), ("quick", quick_sort)):
    p = Probe(data[:])
    sort(p)
    print(name, p.a == sorted(data), p.cmp, p.miss)
# heap True 3019606 812798
# quick True 2047865 92802

costs = []
for xs in (list(range(2000)), [5] * 2000):     # sorted, then all equal
    for sort in (heap_sort, lambda p: quick_sort(p, first_pivot=True)):
        p = Probe(xs[:])
        sort(p)
        costs.append(p.cmp)
print(costs)                                   # [39159, 1999000, 5994, 1999000]

ok = True
for _ in range(2000):                          # small arrays, many duplicates
    xs = [random.randint(0, 9) for _ in range(random.randint(0, 40))]
    for sort in (heap_sort, quick_sort):
        p = Probe(xs[:])
        sort(p)
        ok &= p.a == sorted(xs)
print(ok)                                      # True

On random data, heap sort made about 1.5 times as many comparisons — and nearly nine times as many simulated cache misses. Each sift compares two children and a parent at every level, and each level is a long jump. That second number is why heap sort is typically slower on real hardware despite matching quick sort's Big-O.

The second line is where the heap earns its keep. With the first element as pivot, already-sorted input sends quick sort to 1,999,000 comparisons for 2,000 values — exactly n(n − 1)/2, fully quadratic. Heap sort does 39,159. And the all-equal input breaks this partition even with a good pivot: nothing is smaller than the pivot, so every split is maximally lopsided. Heap sort shrugs.

The complexity

• Heap sort: O(n log n) worst, average and best (apart from inputs like all-equal, where sifts stop at once). O(1) extra memory. Not stable.
• Quick sort: O(n log n) expected with random pivots, O(n²) worst. O(log n) stack when you recurse on the smaller side, as above. Not stable.
• Building the heap: O(n), not O(n log n) — most nodes are near the bottom and sift only a step or two. The heapify lesson walks through why.

Where it goes wrong

• Instability. Sifting flings equal keys across the array, so records with the same key can come out in a different order than they went in. If order among equals matters, use a stable sort.
• Off-by-one in the children. Zero-based arrays put children at 2i + 1 and 2i + 2. Mixing in the one-based 2i formula silently corrupts the heap.
• Forgetting to shrink the heap. Sifting over the full length after a swap drags the finished maximum back into play.
• Quick sort on duplicates. A two-way partition like the one above degrades on many equal keys. A three-way partition, grouping values equal to the pivot in the middle, fixes it.

The practical answer to "which one?" is often both. Introsort, the hybrid behind several C++ standard library sorts, runs quick sort but watches its recursion depth; past about 2 log n levels it switches that range to heap sort. Quick sort's speed on typical data, heap sort's guarantee on adversarial data. The trade-offs against merge sort are covered in merge sort.

How to say it in an interview

"Heap sort is O(n log n) in the worst case and sorts in place, which quick sort can't promise. But its sift-down jumps from index i to about 2i, so its memory access is scattered, and it does more comparisons per element. Quick sort's partition is a sequential scan, which caches love, so in practice quick sort with random pivots is usually faster. Production sorts often combine them: quick sort by default, falling back to heap sort when recursion gets too deep."

That last sentence answers the question the interviewer was really asking: not which is better, but what each one is for.