Insertion sort

Python sorts a list for you with sorted and sort, and in your own programs they're almost always the right tool. So why learn how sorting works? The ideas inside the classic sorting algorithms come back in many other problems: growing a part that is already solved, splitting a problem in halves, putting one item in its final place. Interviewers ask about them, and knowing what each one costs tells you which tool fits. This module builds the classic sorts one by one and ends with Python's own.

Sorting cards in your hand

Insertion sort sorts a list the way many people sort a hand of cards: take the cards one at a time, and slide each new card left past the bigger ones until it sits in its place. The cards to the left of the new one are always in order, a sorted part that grows by one card each round.

In a list, sliding left means moving each bigger item one place to the right, which opens a gap, and then dropping the new item into the gap. Each item moved is one move. This program prints the list after each round, with the number of moves the round made:

values = [4, 8, 1, 6, 3]
print(values)
for i in range(1, len(values)):
    item = values[i]
    j = i
    while j > 0 and values[j - 1] > item:
        values[j] = values[j - 1]
        j -= 1
    values[j] = item
    print(values, "moves:", i - j)

[4, 8, 1, 6, 3]
[4, 8, 1, 6, 3] moves: 0
[1, 4, 8, 6, 3] moves: 2
[1, 4, 6, 8, 3] moves: 1
[1, 3, 4, 6, 8] moves: 3

The 8 already sits after the 4, so the first round leaves the list as it was. The 1 is the smallest item so far: the 8 and the 4 both step right, and the 1 lands at the front. The 6 slides past the 8 alone, because the 4 before it is smaller. The 3 slides past 8, 6 and 4 and stops behind the 1.

Why is the result sorted? Before round i, the items values[:i] are in order. The round puts values[i] among them in its right place, so after the round values[:i + 1] is in order. After the last round, that's the whole list.

What it costs

Each move puts right exactly one pair of items that was in the wrong order, a bigger item before a smaller one. Such a pair is an inversion, and insertion sort makes exactly as many moves as the list has inversions:

• A list in reverse order has every pair the wrong way round. Round i makes i moves, n(n - 1) / 2 in all: O(n²). For 100,000 values that's about 5 billion moves, many minutes in Python.
• A sorted list has no inversions. Each round compares once and stops: n - 1 comparisons, O(n).
• A nearly sorted list, where every item is at most a few places from where it belongs, is O(n) too: each round makes only a few moves.

So insertion sort is slow in general but quick on data that is almost in order. It needs no extra memory, O(1), since it works inside the list. And equal items never pass each other, because > stops at an equal item.

The mistake that throws the speed away

The while loop stops at the first item that isn't bigger, and that's what makes the nearly sorted case fast. A common way to write insertion sort swaps neighbors in a for loop that always runs to the front of the list:

def stops_early(values):
    comparisons = 0
    for i in range(1, len(values)):
        item = values[i]
        j = i
        while j > 0:
            comparisons += 1
            if values[j - 1] <= item:
                break
            values[j] = values[j - 1]
            j -= 1
        values[j] = item
    return comparisons


def never_stops(values):
    comparisons = 0
    for i in range(1, len(values)):
        for j in range(i, 0, -1):
            comparisons += 1
            if values[j - 1] > values[j]:
                values[j - 1], values[j] = values[j], values[j - 1]
    return comparisons


print(stops_early(list(range(1000))), never_stops(list(range(1000))))
print(stops_early(list(range(1000, 0, -1))), never_stops(list(range(1000, 0, -1))))

999 499500
499500 499500

Both sort correctly, and on a list in reverse order they do the same work. But never_stops keeps comparing after the item has found its place, so a sorted list costs it n(n - 1) / 2 comparisons too: O(n²) always. For 200,000 sorted values that's 20 billion comparisons, many minutes, where stops_early needs 199,999. The inner loop has to stop: with the condition in the while, or with a break.