Sorting — Insertion Sort

By the end of this lesson you can:

• Implement insertion sort with an outer loop + inner shifting loop.
• Trace through the "take a card, slot it in" mental model.
• Recognise that insertion sort is O(n²) worst case but O(n) best case (nearly-sorted input).
• Know that Python's Timsort uses insertion sort internally for small chunks — proving its worth.

Start:    [5, 3, 8, 1, 4]
           ↑ first card is "sorted" by itself

Take 3:   compare to 5; smaller; slot before → [3, 5, 8, 1, 4]

Take 8:   compare to 5; bigger; stays         → [3, 5, 8, 1, 4]

Take 1:   compare to 8 (smaller), 5 (smaller),
          3 (smaller), goes at the start       → [1, 3, 5, 8, 4]

Take 4:   compare to 8 (smaller), 5 (smaller),
          3 (bigger), slot after 3             → [1, 3, 4, 5, 8]

You've done this with a real deck of cards. The left side of your hand stays sorted as you go.

The shape

def insertion_sort(lst):
    for i in range(1, len(lst)):
        current = lst[i]                  # the card we're slotting
        j = i - 1
        # Shift larger elements right
        while j >= 0 and lst[j] > current:
            lst[j + 1] = lst[j]
            j -= 1
        lst[j + 1] = current               # slot the card in

data = [5, 3, 8, 1, 4]
insertion_sort(data)
print(data)        # [1, 3, 4, 5, 8]

Five lines inside the for-loop. current holds the card we're placing. The inner while shifts bigger neighbours right. lst[j + 1] = current drops the card into its slot.

Why it's faster than bubble in practice

Bubble does a swap (3 operations) every time it finds an out-of-order pair. Insertion does only one comparison and a shift (1 operation) per misplaced item. Both are O(n²) — but the constant factor for insertion is much smaller.

The best case · already sorted

If the list is already sorted, the inner while never fires (because lst[j] < current immediately). The outer loop runs N-1 times with constant work each. O(n) — linear time.

# Already sorted — insertion sort is O(n)
data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
insertion_sort(data)     # nearly instant — one comparison per item

Bubble sort, even with the early-exit optimisation, would still do one full pass (O(n) comparisons) before knowing. Insertion is faster in this case.

The worst case · reverse-sorted

Every new item has to slide all the way to the start. O(n²).

Stable sort

Insertion sort is stable — equal elements keep their original relative order. We only shift when lst[j] > current (strict). On equal, we stop. This matters when sorting by a secondary key and you want to preserve a primary order.

students = [("Aisyah", "A"), ("Wei Jie", "B"), ("Priya", "A"), ("Iman", "B")]
# Sort by grade — stable sort keeps name order within each grade
insertion_sort_key(students, key=lambda s: s[1])
# Stable result: [("Aisyah", "A"), ("Priya", "A"), ("Wei Jie", "B"), ("Iman", "B")]

Where insertion sort still wins today

✓ Small lists (≤ ~20 items)              fastest in practice
✓ Almost-sorted lists                     near O(n)
✓ Streaming data — items arrive one       insert as they come
   at a time
✓ As a sub-routine inside Timsort         Python uses it for runs ≤ 64

Timsort (Python's built-in) actually uses insertion sort internally. When it spots a small run (≤ 64 items), it calls insertion sort because it's genuinely faster than mergesort or quicksort at that scale.

Save as insertion_visual.py:

# insertion_visual.py — print every step

def insertion_sort_visual(lst):
    print(f"Start: {lst}")
    for i in range(1, len(lst)):
        current = lst[i]
        j = i - 1
        while j >= 0 and lst[j] > current:
            lst[j + 1] = lst[j]
            j -= 1
        lst[j + 1] = current
        sorted_part = lst[:i + 1]
        unsorted_part = lst[i + 1:]
        # Visual separator between sorted (left) and unsorted (right)
        joined = " ".join(str(x) for x in sorted_part) + " | " + \
                 " ".join(str(x) for x in unsorted_part)
        print(f"Step {i}: take {current}, place →  [{joined}]")


insertion_sort_visual([5, 1, 4, 2, 8, 3])

Output

Start: [5, 1, 4, 2, 8, 3]
Step 1: take 1, place →  [1 5 | 4 2 8 3]
Step 2: take 4, place →  [1 4 5 | 2 8 3]
Step 3: take 2, place →  [1 2 4 5 | 8 3]
Step 4: take 8, place →  [1 2 4 5 8 | 3]
Step 5: take 3, place →  [1 2 3 4 5 8 | ]

Read the diff

After each step, the left of | is sorted; the right is still raw. The boundary moves right by one each pass. Five passes for six items.

Insertion sort takes each item one at a time and shifts it left into the sorted portion. O(n²) worst case, O(n) best case (already sorted). Stable — equal elements keep order. Faster in practice than bubble sort. Still used inside Python's Timsort for small runs. For real sorting work in production: never write your own — use sorted(). We'll meet it tomorrow.