¿Por que un array ordenado se ejecuta más rápido?. Por Branch Prediction

Aquí está un pedazo de código de C ++ que parece muy peculiar. Por alguna extraña razón, ordenar los datos milagrosamente hace que el código casi seis veces más rápido.