Heapsort and quicksort both do about n log n comparisons — why does heapsort lose the benchmark?
answer
- count operations, then count cache misses
- where does index i send you next?
- 2i+1 grows fast, strides explode
- partitioning streams, sift-down scatters
- recursion shrinks the working set
basics
~20 sMemory access patterns, not operation counts. Sift-down jumps from index i to 2i+1, so each step lands far away and misses cache once the array outgrows it, while partitioning scans sequentially and prefetches perfectly. Same asymptotics, very different constants.
solid answer
~50 sBig-O hides the constant, and here the constant is the memory hierarchy. Sift-down walks a root-to-leaf path whose indices double at every level, so consecutive accesses are separated by growing strides; once the heap is larger than the last-level cache, most levels of most sift-downs are cache misses, and the cache lines fetched are largely wasted because the siblings you also loaded are never needed. Partition-based sorting does the opposite: two sequential scans over a contiguous range, which hardware prefetchers handle perfectly, and once a subrange fits in cache the entire recursion below it runs hot. Heapsort also branches unpredictably on which child is larger, costing mispredictions. The result is that heapsort commonly runs a small multiple slower on large arrays despite an identical comparison count — which is exactly why it survives in production as a *fallback* that caps the worst case rather than as the default.
code
pseudocode · 10 lines// restore the max-heap property from index i downwards
while 2*i + 1 < size
child = 2*i + 1 // stride doubles each level
if child + 1 < size and a[child + 1] > a[child]
child = child + 1 // data-dependent branch
if a[i] >= a[child]
break
swap(a[i], a[child])
i = child
...go deeper
Take away one idea: two algorithms with the same big-O can differ several-fold in real time, because memory access patterns and constant factors are not in the notation.
Explain the access pattern concretely — index i jumps to 2i+1, so the stride grows with depth — and contrast it with a sequential scan that a prefetcher can follow.
Show how you would confirm the diagnosis: size sweeps around cache capacity, hardware counters for misses and mispredictions, and testing inline values versus scattered references.
Own the design conclusion: keep the cache-friendly sort as the default and use the guaranteed-bound sort as a depth-triggered fallback, and be able to justify the extra code paths that hybrid costs.
## Same asymptotics is not same speed Asymptotic notation deliberately discards constant factors, and on modern hardware the constant factor is dominated by where the data is, not by how many comparisons you do. A last-level cache hit costs a handful of cycles; a main-memory access costs on the order of a hundred or more. An algorithm that does the same number of comparisons but suffers a cache miss on most of them will lose badly, and no amount of asymptotic analysis will predict it. ## What sift-down does to the memory hierarchy The access pattern is the whole story. Sift-down starts at index `i` and moves to `2i+1` or `2i+2`, repeatedly: - Near the root, successive indices are 0 → 1 → 3 → 7 → 15 — close together, likely on the same or nearby cache lines. - Deep in the tree, they are separated by hundreds of thousands of elements. Each step is a fresh, unpredictable address. So one sift-down over a heap much larger than cache generates roughly one miss per level below the point where the working set stops fitting — about log(n) minus log(cache capacity in elements) misses. Worse, every miss loads a full cache line of neighbouring elements, and in the implicit heap layout those neighbours are the node's *sibling subtrees*, which this sift-down will never visit. The bandwidth is spent and thrown away. The access sequence is also unpredictable to the hardware prefetcher, because which child you descend into depends on a data comparison. There is no stride to detect. The same comparison makes the branch itself unpredictable — roughly a coin flip on random data — so the pipeline pays for mispredictions on top of the misses. ## What partition-based sorting does instead Partitioning sweeps two cursors toward each other over a contiguous range. Every access is one element past the previous one, in a direction the prefetcher recognises immediately (forward and backward streaming are both handled well). Each cache line that is loaded is fully consumed before it is evicted. And there is a second, larger effect: recursion narrows the range, so after a few levels the subarray fits entirely in cache, and *all* the work below that point — which is most of the total work, since the tree is bottom-heavy — runs at cache speed. Heapsort has no such phase; its working set is the whole array from the first extraction to the last. A fair scorecard for large arrays: | Aspect | Heapsort | Partition-based sorting | |---|---|---| | Comparison count | ~2n log n | ~1.4n log n average | | Access pattern | index doubling, scattered | sequential, prefetch-friendly | | Branch predictability | poor (which child is larger) | poor at partition, but fewer levels of it | | Working set shrinks? | no | yes, subranges become cache-resident | | Worst case | O(n log n) guaranteed | O(n^2) with weak pivots | ## Why this is a senior-level answer, not trivia The misconception being tested is "same big-O means same speed", and it has practical consequences beyond sorting: it is why linked structures lose to contiguous ones for traversal, why blocked matrix algorithms beat naive ones with identical operation counts, and why micro-optimising comparison counts is usually the wrong lever. If you are diagnosing a slow sort, the questions are: how large is the data relative to cache, is the access pattern streaming or scattered, and is the comparison itself chasing pointers to somewhere else in memory (which adds another indirection to every step and can dwarf the sort's own pattern). Note also what heapsort's profile does *not* mean. Its O(n log n) worst case is real and quicksort's O(n^2) is real; the benchmark loss is an average-case phenomenon. That is precisely why the mainstream engineering answer is a hybrid: run the fast, cache-friendly partitioning sort, count recursion depth, and switch to heapsort only when the depth suggests a pathological pivot sequence. That algorithm — introsort — is what several mainstream standard libraries ship for value types, while others default instead to a stable adaptive merge-based sort (the Timsort family) for reference types; C++ and Java made visibly different calls here for different element kinds, and both are defensible given what their callers can observe. ## Measuring it honestly If you claim the cache is the cause, prove it rather than asserting it: run the same sorts at sizes spanning well below and well above last-level cache capacity and watch where the curves diverge; count cache misses and branch mispredictions with a hardware counter profiler; and sort an array of small inline values versus an array of references to scattered objects, which changes the locality story completely.
- At what input size would you expect the two sorts' measured times to converge?Roughly where the whole array fits comfortably in cache. Below that, both are working out of fast memory and the difference collapses to comparison counts and branch behaviour; heapsort's ~2n log n comparisons still cost something, but the gap narrows sharply. The divergence appears as the array grows past last-level cache capacity, which is exactly the experiment to run before making the claim.
- Does this cache argument change if the array holds references to objects scattered in memory rather than inline values?Yes, and mostly it flattens the difference. If every comparison chases a pointer to an unpredictable address, both sorts pay a miss per comparison and the sort's own access pattern stops dominating. The right fix then is not swapping sort algorithms but making the compared key cheap and local — for example sorting extracted key-plus-position pairs rather than the records themselves.
Sift-down is a library visitor who reads one page per floor, taking the stairs between distant floors each time; partitioning is a visitor who reads one whole shelf end to end.
saying these in an interview costs you the question
- Says equal big-O implies equal runtime
- Attributes the gap purely to comparison counts
- Claims heapsort's array layout makes it cache-friendly
- Ignores prefetching and branch prediction entirely
- Concludes heapsort is useless in production