Why Is a Sorted Array Faster? Branch Prediction Explained (Stack Overflow Classic)
Deep dive · 11:07 · Computer science · Watch on YouTube
Big-O says sorting first is extra work: O(n log n) on top of an O(n) loop. Yet in one of the most upvoted questions on Stack Overflow, the same loop ran 6× faster on sorted data. I re-measured it on an Apple M4 Max: 8.6×. This video explains why, with real measurements at every step, and with the best answers from the thread.
You'll see
- why cache, summation order and language are not the reason
- how a CPU pipeline works, and why an if statement breaks it
- Mysticial's railroad junction analogy, animated
- the 2-bit saturating counter, run on the benchmark's real data
- cachegrind's 25% mispredict rate, and why it's 25% and not 50%
- the cost of one wrong guess on an M4: about 3.7 ns, or 17 clock cycles
- why partitioning is enough, and why Big-O isn't actually wrong
- branchless code: the bit trick, cmov / csel, lookup tables, and one trick that backfires
- what compilers do: if-conversion, Intel's loop interchange, and SIMD vectorization
Sources & notes
Original question on Stack Overflow:
https://stackoverflow.com/questions/11227809
Every number is real. Thread figures and quotes come from "Why is processing a sorted array faster than processing an unsorted array?" (Stack Overflow, CC BY-SA; answers by Mysticial, WiSaGaN, caf, steveha, vulcan raven, Saqlain and others, plus comments by Peter Cordes and Šimon Hrabec). Timings were measured on an Apple M4 Max with clang 17. Predictor behaviour is simulated on the benchmark's exact data. Animations are made with Python and Manim.