The answer focuses on branch misprediction but there is also another factor - CPU data prefetch. In order to offset increasing CAS latencies (largely due to th

The answer focuses on branch misprediction but there is also another factor - CPU data prefetch. In order to offset increasing CAS latencies (largely due to the increasing number of channels) modern CPU's are greedy (in a good sense) and fetch more pages per memory controller read request than are necessary. If your data is laid out continuously (in this case - sorted), chances of the pages you need next being primed via prefetch are greatly increased and further read requests to the memory controller may be reduced or avoided. I benchmarked the effect of data prefetching on modern processors with large data structures (usually limited to L1d cache lines): https://github.com/johnj/llds#l1-data-prefetch-misses-200000-per-hardware-sample https://github.com/johnj/llds#l1-data-prefetch-misses-200000... A plausible analogy for CPU prefetching would be "readahead" mechanisms implemented by modern filesystems and operating systems.