Heapsort and Cache Locality

Heapsort is $O(n\log n)$ in every case, and it is in-place. But libraries rarely choose it first, and the reason is something the Big-Oh does not measure: how the algorithm uses memory. The quadratic sorting chapter named this idea, cache locality, but did not explain it.

How memory reads work

Reading from memory does not always cost the same, even though our analysis counts every read as one step. The processor keeps a small, fast store of recently used data, called a cache. When it reads one location from main memory, it brings in a whole neighborhood of nearby locations with it and keeps them in the cache.

So the order of your reads matters. Reading through memory in order is cheap: each read is close to the last one, so it is already in the cache. Reading scattered locations is expensive: each read can miss the cache, and the processor has to go to main memory, which is slow, and bring in a new neighborhood.

Where heapsort reads

Most of heapsort’s work is in sink, which steps from a node at index $i$ to a child at $2i+1$ or $2i+2$. Near the top of the tree those are close together. But the deeper the sink goes, the farther apart a node and its child are. Follow one sink down the left edge of an eight-element heap; it touches indices $0,1,3,7$:

  0   1   2   3   4   5   6   7
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ … │ … │ … │ … │ … │ … │ … │ … │
└───┴───┴───┴───┴───┴───┴───┴───┘
  •──▶•──────▶•──────────────▶•
gaps double each level: scattered

On a large heap those jumps reach a different neighborhood almost every time, so almost every step misses the cache and has to read from main memory.

Where merge sort reads

Merge sort’s merge reads two sorted halves from left to right, one element after the other, and writes the result in order as it goes. That is the in-order pattern, so almost every read is already in the cache from the last fetch.

  0   1   2   3   4   5   6   7
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ … │ … │ … │ … │ … │ … │ … │ … │
└───┴───┴───┴───┴───┴───┴───┴───┘
  •──▶•──▶•──▶•──▶•──▶•──▶•──▶•
neighbors, +1 each step: sequential

So merge sort and heapsort have the same $O(n\log n)$ running time, but merge sort is usually faster in practice.

The other sorts

The quadratic sorts read through memory in order too. Bubble sort compares and swaps neighbors, arr[j] and arr[j + 1], from left to right. Insertion sort shifts larger values one slot to the right as it scans back through the sorted part, so the slots it touches are next to each other. Selection sort scans the unsorted part from left to right to find the largest value. Its swap into the last unsorted slot can cross a long gap, but there is only one such swap per pass, about $n$ in the whole sort, and the scans that do the reading stay in order.

So four of the five sorts read memory in order: bubble, selection, insertion, and merge. Heapsort is the one that scatters its reads. On real hardware, those scattered reads are why heapsort is usually slower than a sort that reads memory in order.