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):
While prefetch is an important factor, it is not the case here since the data array is accessed sequentially in both the sorted or unsorted scenarios. Also the initial number generation loop already primes the data in the memory for either scenario.
Comments
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...
A plausible analogy for CPU prefetching would be "readahead" mechanisms implemented by modern filesystems and operating systems.
While prefetch is an important factor, it is not the case here since the data array is accessed sequentially in both the sorted or unsorted scenarios. Also the initial number generation loop already primes the data in the memory for either scenario.