Insertion sort

Simple sorts · Article 3 of 8 · 4 min read

Sort the way you sort playing cards, and see why nearly sorted data is cheap.

The short version

Insertion sort keeps a sorted section at the front. It takes the next item and slides it left until it sits in the right place.

Details

On a list that is already sorted, each item stays put, so the work is linear. On a reversed list it is n squared. Insertion sort is stable and is often used for very small lists.

Try it yourself

def insertion_sort(items):
    for i in range(1, len(items)):
        current = items[i]
        j = i - 1
        while j >= 0 and items[j] > current:
            items[j + 1] = items[j]
            j -= 1
        items[j + 1] = current

data = [5, 2, 9, 1]
insertion_sort(data)
print(data)

You should see [1, 2, 5, 9].

Explain it to the duck

Why is insertion sort fast on a list that is almost sorted?

Tested with: Python 3.13.