How sorting works and what it costs

You will use the ready-made function, but it is worth seeing once what goes on inside. The plainest method is insertion sort: as when ordering cards in your hand, you slide each new element into its place in the sorted part to its left.

1for i in range(1, len(values)):
2    x = values[i]
3    j = i - 1
4    while j >= 0 and values[j] > x:
5        values[j + 1] = values[j]
6        j -= 1
7    values[j + 1] = x

x is set aside; those larger than it each move one to the right; x is written into the gap that opens. When the loop ends j points at the last element not larger than x; the gap is one to its right.

In the worst case (a list in reverse order) this method takes n × n steps. Good methods, the one Python uses among them, take n log n: for a million elements, twenty million steps instead of a trillion. The thing to remember: sorting once is cheap, and after sorting every search drops to log n with binary search. For n queries, "sort, then search" comes to n log n in all.

Tasks