Why is it faster to process a sorted array than an unsorted array?

And a python quirk:

Prints:

C:\_\Python27\python.exe C:/Users/MrD/.PyCharm2016.2/config/scratches/timeit_key_tuple_sorting.py
***** STRINGS
0.683437665535
0.659069905351
0.578510675866
***** INTS
0.116263496833
0.200527380123
0.160531444582
***** OBJECTS
9.64448849458
7.22313209823
6.99353018193
***** BONUS range vs xrange and inlining length
3.16139231018
3.13278352095
2.18729023897
2.16974310625

For an explanation see Why is sorting a python list of tuples faster when I explicitly provide the key as the first element?. Note that for int keys the non key way is still faster - apparently the overhead of lambda (or even itemgetter) compared to int comparison is significant.