Why is it faster to process a sorted array than an unsorted array? (2012)
The question I have, which I do not see answered after a quick glance of the top responses, is: What is the total time of sorting + good branch prediction loop, versus not sorting and bad branch prediction loop?  Does the good branch prediction save more time than it cost to sort the array, on modern processors?  What about old processors with shorter pipelines?