Sorting made this loop 8× faster. Big-O says it shouldn't.
Short · 1:41 · 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 one of the most upvoted questions on Stack Overflow found the loop runs 6× faster on sorted data. On an M4 Max today, it's 8.6×.
The reason is branch prediction: your CPU guesses which way every if goes, and on random data it guesses wrong half the time.
Sources & notes
Source: "Why is processing a sorted array faster than processing an unsorted array?", Stack Overflow (CC BY-SA)
https://stackoverflow.com/questions/11227809
Timings measured on an Apple M4 Max.