Insertion Sort

AQA 4.3.5 — Insertion sort

Retrieval: Bubble sort repeatedly swaps adjacent pairs across the whole list. Insertion sort takes a different approach entirely: it grows a sorted section one item at a time, inserting each new item directly into its correct position within that section.

Conceptually, the list is split into a sorted partition (at the start, initially just the first item) and an unsorted partition (the rest). Each step takes the next unsorted item and shifts sorted items rightward until it can insert that item into its correct place.

def insertion_sort(items):
    for i in range(1, len(items)):
        key = items[i]
        j = i - 1
        while j >= 0 and items[j] > key:
            items[j + 1] = items[j]   # shift a sorted item rightward
            j -= 1
        items[j + 1] = key             # insert key into its correct gap
    return items

Common mistake

Confusing insertion sort's shift-and-insert process with bubble sort's repeated adjacent swaps — they're taught back-to-back precisely because they're easy to conflate. Bubble sort compares neighbouring pairs across the whole list every pass; insertion sort only ever works on extending its sorted partition by one item, shifting as needed.

Trace it

Tracing insertion_sort([5, 2, 4, 1]):

Step	key	Sorted partition after step
`i=1`	2	[2, 5, 4, 1] — 2 shifts left past 5
`i=2`	4	[2, 4, 5, 1] — 4 shifts left past 5, stops before 2
`i=3`	1	[1, 2, 4, 5] — 1 shifts left past 5, 4 and 2

Compare insertion sort with bubble sort

	Bubble sort	Insertion sort
Core operation	Swap adjacent out-of-order pairs	Shift sorted items, insert into correct gap
Best case (already sorted)	Still checks every pair unless optimised (previous lesson)	Very fast — each item requires zero shifts
Typical use	Simple to explain and trace	Efficient for data that's already nearly sorted

Challenge

Trace insertion_sort([1, 2, 3, 4]) — a list that's already sorted. Count how many times the while loop's body actually executes (shifts happen). Compare this to how bubble sort's unoptimised version would still perform every comparison in every pass on the same input, even though nothing needs to move.

Looking ahead: the final lesson of this sequence (Algorithm Performance) puts these observations on a firmer footing — comparing bubble sort and insertion sort (and linear vs binary search) using real counted operations, not just informal impressions.

Learn

AQA 4.3.5 — Insertion sort

Common mistake

Trace it

Compare insertion sort with bubble sort

Challenge

Practise

Test yourself