Why Quick Sort Is Faster in Practice

Reading a value from memory is not one operation with one cost. It is a lookup through a hierarchy, and the levels differ enormously:

• CPU registers — effectively free.
• L1 cache (tens of KB) — roughly 1 nanosecond.
• L2 cache (hundreds of KB) — a few nanoseconds.
• L3 cache (several MB, usually shared) — around 10-20 nanoseconds.
• Main memory (RAM) — around 60-100 nanosecond.

So a cache miss can cost about a hundred times more than a cache hit. Big O counts both as "one memory access". That is not a flaw; abstracting hardware away is the point. But it means two O(n log n) algorithms can differ by a large constant, and that constant is decided by cache behaviour.

Crucially, the CPU does not fetch single values. It fetches a cache line, typically 64 bytes — sixteen 32-bit integers at once. It also runs a prefetcher that notices sequential access patterns and speculatively pulls the next lines in before you ask. Both mechanisms reward code that walks memory in order and punish code that jumps around.

Quick Sort's inner loop is a partition: two indices walk toward each other through one contiguous slice of the array, comparing against the pivot and swapping. That is about as cache-friendly as an algorithm can be.

• It works in place — there is only one array, so there is only one region of memory competing for cache.
• Access is sequential in both directions, so the prefetcher predicts it accurately and the data arrives before it is needed.
• Each fetched cache line is fully used: pull in sixteen integers, compare all sixteen, move on. No waste.
• Recursion narrows the working set. As sub-arrays shrink, they eventually fit entirely in L1, and the deepest — most numerous — levels of the recursion run at full speed.

That last point is easy to miss and does a lot of work. Roughly half of all Quick Sort calls operate on sub-arrays small enough to sit wholly in L1 cache, so the bulk of the recursion tree runs on the fastest memory the machine has.

Merge Sort's merge step is also sequential — which is why it is excellent on disk — but it has a structural cost Quick Sort does not:

• It needs O(n) auxiliary space, so at every level it is reading from two source regions and writing to a third. Three streams compete for the same cache instead of one.
• Data is copied between the array and the buffer, which is real work that produces no comparisons.
• At the top levels the regions being merged are far larger than cache, so lines are evicted before they are reused.
• Merging reads two runs at once, and interleaving two sequential streams is harder on the prefetcher than following one.

Add it up and the practical figure on a modern machine sorting a million random 32-bit integers is roughly 80-100 ms for Quick Sort against 200-250 ms for Merge Sort. Same Big O, same comparison count to within a small factor, about 2.5x the wall-clock time. The difference is almost entirely memory traffic.

The advantage is conditional, and knowing the conditions is the actually useful part.

On disk, Merge Sort wins outright. Once the data does not fit in RAM, the relevant hierarchy step is RAM-to-storage rather than cache-to-RAM, and the gap is thousands of times rather than a hundred. Merging reads runs strictly sequentially, which storage handles well; Quick Sort's partitioning seeks all over the file. This is exactly why every database uses external merge sort.

On linked lists, Merge Sort wins. There is no contiguous memory to be cache-friendly about, Quick Sort loses its random access, and merging is just pointer rewiring — with no auxiliary array needed at all.

On partly-ordered data, Tim Sort wins. Cache behaviour is irrelevant if a competitor can skip most of the work. Tim Sort detects existing runs and can approach O(n); Quick Sort does the full job regardless of input. See Quick Sort vs Tim Sort.

On GPUs, Radix Sort wins. Different hardware, different reward function: massively parallel machines punish branching and unbalanced work, both of which Quick Sort has.

Adversarial input. With a naive pivot, Quick Sort degrades to O(n²) — at which point no amount of cache friendliness helps. This is why real implementations randomise the pivot or bound the recursion depth; see pivot selection strategies.

Once you can see cache locality, you find it everywhere, and it is usually the explanation for a benchmark that "makes no sense".

Arrays vs linked lists. Traversing a linked list and traversing an array are both O(n), but the array is commonly several times faster: its elements are adjacent, so each cache line delivers many of them, whereas list nodes are scattered and each one may cost a miss. This is why std::vector beats std::list for iteration even when the list would have better insertion complexity.

Row-major vs column-major traversal. Looping over a 2D array in the order it is actually stored can be an order of magnitude faster than looping the other way. Identical operation count, identical Big O — one walks memory sequentially and the other strides across it, touching a new cache line every single step.

Struct of arrays vs array of structs. Game engines and data-oriented systems store fields in separate arrays precisely so that a loop touching one field does not drag the other fields into cache with it.

The general rule: Big O tells you how an algorithm scales; memory layout tells you how fast it actually is. You need the first to avoid catastrophe and the second to be genuinely fast.

Three things worth keeping.

First, Big O is necessary but not sufficient. It correctly tells you an O(n²) sort will die on large input. It cannot tell you which of two O(n log n) sorts to prefer, because it has deliberately discarded the information that decides it.

Second, when two algorithms share a complexity class, compare their memory access patterns. Sequential beats scattered; in-place beats copying; a small working set beats a large one. That heuristic will predict the winner most of the time.

Third, this is why interview answers should be phrased with the reason attached. "Quick Sort is usually faster in practice because it sorts in place with sequential access that stays in cache, while Merge Sort copies into an O(n) buffer and misses cache more often — but Merge Sort wins on disk, on linked lists, and whenever stability is required" is a complete, senior-sounding answer, and it is complete precisely because it explains the mechanism rather than reciting the outcome.