What is the time complexity of the heap-building phase in heapsort (transforming an unsorted array into a max-heap)?
AO(n log n) — each of the n elements must be sifted through up to log n levels
BO(n) — most nodes are near the bottom of the heap with little or no sifting required
CO(n²) — each element must be compared against all previously inserted elements
DO(log n) — only the root requires a full sift-down
The O(n log n) intuition fails because not all nodes sift the full tree height. About half the nodes are leaves (zero sift work), a quarter are one level up, an eighth two levels up, and so on. The total work is Σ(h=0 to log n) (n/2^(h+1))·h, a convergent geometric series summing to O(n). This is the non-obvious result: even though each sift-down is O(log n), the structure of the heap ensures most sift-downs are cheap. The extraction phase — n−1 extract-max calls — is what contributes O(n log n).
Question 2 Multiple Choice
Heapsort guarantees O(n log n) worst-case performance. Why do many standard library sort implementations use quicksort-based algorithms instead?
AQuicksort has better average-case complexity than O(n log n)
BHeapsort's access pattern causes frequent cache misses, making it slower in practice despite its better worst-case guarantee
CQuicksort is in-place while heapsort requires O(n) auxiliary space
DHeapsort is less numerically stable than quicksort for floating-point keys
Heapsort's sift-down accesses parent at index i and children at 2i+1 and 2i+2. For a large heap, these are far apart in memory, causing frequent cache misses. Modern CPUs rely on spatial locality — sequential access hits the cache; random jumps don't. Quicksort's partitioning phase accesses contiguous subarrays, which fits well into cache lines. Both sort in-place with O(1) auxiliary space, so that isn't the distinction. In practice, introsort (quicksort with a heapsort fallback for worst-case protection) is the common compromise.
Question 3 True / False
Heapsort is a stable sorting algorithm — equal elements preserve their relative order from the input in the sorted output.
TTrue
FFalse
Answer: False
Heapsort is not stable. During extraction, the maximum element is swapped to the end of the unsorted portion, and the subsequent sift-down can move equal-valued elements past each other without tracking their original order. Stability requires that equal elements never overtake each other, which heapsort's swap-and-sift mechanism does not guarantee. When stability is required, merge sort (stable, O(n log n), but O(n) auxiliary space) is the standard alternative.
Question 4 True / False
Heapsort's extraction phase runs in O(n log n) because each of the n−1 extract-max operations requires an O(log n) sift-down.
TTrue
FFalse
Answer: True
After building the heap, you perform n−1 extract-max operations: swap the root with the last unsorted element, shrink the heap by one, then sift-down the new root to restore the heap property. Sift-down on a heap of size k takes O(log k). Since k decreases from n−1 to 1, total work is Σ(k=1 to n−1) log k ≈ n log n. This phase dominates the O(n) build phase, giving O(n log n) overall.
Question 5 Short Answer
Explain why heapsort's O(n log n) worst-case guarantee comes with a real-world performance cost, using the concept of cache locality.
Think about your answer, then reveal below.
Model answer: Heapsort's sift-down operations access a node and its children at indices i, 2i+1, and 2i+2. For a large heap, these indices are far apart in memory — a node near the root has children near position n/2. Modern CPUs load memory in cache lines (contiguous blocks); when accesses jump across the array, each one likely misses the cache and requires a slow fetch from main memory. Quicksort's partitioning scans a contiguous subarray, keeping most accesses within the same cache lines. This cache advantage makes quicksort faster in practice despite its O(n²) worst case.
Big-O hides constant factors and memory access patterns, both of which matter enormously on real hardware. Cache misses can cost 100× more than cache hits. Heapsort and merge sort both offer O(n log n) guarantees but have different access patterns; merge sort is often faster than heapsort in practice despite using O(n) extra space. The lesson: theoretical complexity is necessary but not sufficient for predicting real performance.