Insertion sort: the place-in algorithm

How it works (spec 10.3.4)

The first item on its own is a sorted section. For each next item (the target): save it, shift every larger item in the sorted section one place right, then place the target in the gap.

The code

def insertion_sort(items):
    for i in range(1, len(items)):
        target = items[i]
        j = i - 1
        while j >= 0 and items[j] > target:
            items[j + 1] = items[j]
            j = j - 1
        items[j + 1] = target
        print("after placing", target, items)

insertion_sort([6, 2, 9, 4, 1])

Output:

after placing 2 [2, 6, 9, 4, 1]
after placing 9 [2, 6, 9, 4, 1]
after placing 4 [2, 4, 6, 9, 1]
after placing 1 [1, 2, 4, 6, 9]

The sample mark scheme credited exactly these parts: an outer loop from index 1, a saved target, a comparator starting one place left, a while loop with two conditions joined by and, shifting larger items right, decrementing the index, and placing the target.

Why j >= 0 comes first

The while condition checks j >= 0 before items[j]. Python's and stops as soon as the first part is False, so items[-1] is never compared by mistake when the target belongs at the very start.

Comparing the sorts

Both bubble and insertion sort are slow on large random lists, since the work grows with the square of n. Insertion sort is fast on lists that are already nearly sorted, because each target needs few shifts. Neither needs a second list.

Worked example

Show the list after each placement when insertion sort is applied to [5, 3, 4, 1].

1. place 3: [3, 5, 4, 1]
2. place 4: [3, 4, 5, 1]
3. place 1: [1, 3, 4, 5]

Answer: [1, 3, 4, 5]

Check yourself

1. What is displayed when this code runs? ```python items = [8, 3, 5, 1] for i in range(1, 3): target = items[i] j = i - 1 while j >= 0 and items[j] > target: items[j + 1] = items[j] j = j - 1 items[j + 1] = target print(items) ```
   Show answer

   [3, 5, 8, 1]. After placing 3 and then 5, the first three items are sorted: [3, 5, 8, 1].

2. How many items are shifted right when the target 2 is inserted into the sorted section of [3, 5, 8, 2, 6]?
   Show answer

   3. 3, 5 and 8 are all larger than 2, so all three shift right.

3. What is the value of position after this code runs? ```python items = [4, 1, 3, 2] for i in range(1, len(items)): target = items[i] j = i - 1 while j >= 0 and items[j] > target: items[j + 1] = items[j] j = j - 1 items[j + 1] = target position = items.index(3) ```
   Show answer

   2. The sorted list is [1, 2, 3, 4], so 3 is at index 2.

4. Which line places the target after the shifting loop ends? ```python def insertion_sort(items): for i in range(1, len(items)): target = items[i] j = i - 1 while j >= 0 and items[j] > target: items[j + 1] = items[j] j = j - 1 __________ data = [9, 4, 7, 1] insertion_sort(data) print(data) ```
   • `items[j] = target`
   • `items[j + 1] = target`
   • `items[i] = target`
   • `items[j + 1] = items[j]`
   Show answer

   `items[j + 1] = target`. When the loop stops, j is just left of the gap, so the target goes at j + 1.

5. Why does the outer loop of insertion sort start at index 1?
   • Index 0 is always the smallest
   • Python lists start at 1
   • The last item never needs sorting
   • A single item at index 0 is already a sorted section
   Show answer

   A single item at index 0 is already a sorted section. The sorted section starts as just the first item.

6. Which list would insertion sort handle with the fewest shifts?
   • [5, 4, 3, 2, 1]
   • [1, 2, 3, 5, 4]
   • [3, 5, 1, 4, 2]
   • [4, 5, 1, 2, 3]
   Show answer

   [1, 2, 3, 5, 4]. A nearly sorted list needs only one shift here; a reversed list needs the most.

7. This code should display [1, 2, 3] but it does not. Which line number contains the error? ``` 1 items = [3, 1, 2] 2 for i in range(1, len(items)): 3 target = items[i] 4 j = i - 1 5 while j >= 0 and items[j] < target: 6 items[j + 1] = items[j] 7 j = j - 1 8 items[j + 1] = target 9 print(items) ```
   Show answer

   5. Line 5 shifts items that are smaller than the target, which sorts into descending order. The comparison should be > target: while j >= 0 and items[j] > target:.

Practise with instant feedback Print this lesson

Sources

• Pearson Edexcel International Advanced Subsidiary/Advanced Level in Computer Science specification (XCP01/YCP01), first teaching 2026
• Pearson IAL Computer Science Unit 2 Programming Language Subset (PLS), Python 3
• Pearson IAL Computer Science IAS sample assessment materials (Unit 2 paper and mark scheme)

Last updated 8 November 2026. Spotted a mistake? Tell us.