Insertion sort in Python

Insertion sort builds a sorted part at the start of the list. It takes the next item, moves the bigger sorted items one place to the right, and puts the item into the gap. This is how many people sort playing cards in their hand.

The program

def insertion_sort(items):
    items = items.copy()               # leave the caller's list unchanged
    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]    # move the bigger item one place right
            j -= 1
        items[j + 1] = current
    return items

numbers = [12, 11, 13, 5, 6]
print(insertion_sort(numbers))
print(numbers)
print(insertion_sort([]))
print(insertion_sort(["Linus", "Ada", "Hedy", "Alan"]))

[5, 6, 11, 12, 13]
[12, 11, 13, 5, 6]
[]
['Ada', 'Alan', 'Hedy', 'Linus']

How it works

• The loop starts at position 1, because a part with one item (position 0) is already sorted.
• current holds the item being inserted. The while loop walks left through the sorted part and moves each bigger item one place to the right.
• The while loop stops at the start of the list (j >= 0) or at an item that is not bigger. items[j + 1] = current puts the item into the gap.
• > (not >=) stops at an equal item, so equal items keep their original order. That makes insertion sort stable.

Watching the steps

items = [12, 11, 13, 5, 6]
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
    print(f"insert {current:>2}: {items}")

insert 11: [11, 12, 13, 5, 6]
insert 13: [11, 12, 13, 5, 6]
insert  5: [5, 11, 12, 13, 6]
insert  6: [5, 6, 11, 12, 13]

Insertion sort needs about n²/2 comparisons in the worst case (a list in reverse order), so it is slow on long, mixed-up lists. But on a list that is already nearly sorted, each item moves only a short way, and on a sorted list it makes just one comparison per item. That is why Python's own sort (Timsort) uses insertion sort for short pieces of the list. Compare it with selection sort and bubble sort. In real code, use sorted(items).