Branch-prediction[
^].
A guess is made whether or not to branch at the if-statement, and for the sorted one most times guessing that the previous way is the way to go will be the correct guess.
Sorting makes it easy for the branch-predictor to get it right.