python-programming / searching-and-sorting · Lesson 25

Lesson 25 — Searching and sorting

Insertion Sort

Build a sorted section by inserting each new value into its correct position.

Insertion sort treats the first item as a sorted section. It then takes each following item and moves it left until it is in the correct position.

Predict

Read the code first. Do not run it yet.

insertion-sort-predict.py

numbers = [3, 7, 5, 9]
value = numbers[2]
position = 2
while position > 0 and numbers[position - 1] > value:
    numbers[position] = numbers[position - 1]
    position = position - 1
numbers[position] = value
print(numbers)

Predict before running

Which value is being inserted?
Which existing value shifts right?
What list is printed?

Investigate

Use this code to explain exactly how the program works.

insertion-sort-investigate.py

numbers = [6, 2, 5]
for current in range(1, len(numbers)):
    value = numbers[current]
    position = current
    while position > 0 and numbers[position - 1] > value:
        numbers[position] = numbers[position - 1]
        position = position - 1
    numbers[position] = value
print(numbers)

Investigate the code

After the first outer-loop repetition, which part is sorted?
Trace the insertion of 5.
What is the final list?

The insertion-sort process

How it works

Treat the first item as the initial sorted section.
Take the next item.
Shift larger items in the sorted section one position to the right.
Insert the current item into the gap.
Repeat until every item has been inserted.

insertion_sort.py

numbers = [6, 2, 5, 1]

for current in range(1, len(numbers)):
    value = numbers[current]
    position = current
    while position > 0 and numbers[position - 1] > value:
        numbers[position] = numbers[position - 1]
        position = position - 1
    numbers[position] = value

print(numbers)

Output

[1, 2, 5, 6]

Understand the behaviourThe key idea is a growing sorted section with each new item inserted into the correct position.

Recognise and apply the algorithmBe able to follow these characteristic steps on a data set and recognise the algorithm from program code. Correct implementations can use different variable names or loop structures, so focus on the behaviour rather than memorising one exact version.

Self-study guide

Insertion sort builds a sorted section one item at a time. Starting from the second item, it saves the current value, shifts larger values in the sorted section one place to the right, then inserts the saved value into the gap.

The defining idea is not “swap neighbours repeatedly” but “take the next item and insert it into the correct place in the already-sorted left section”.

OCR focusUnderstand and apply the insertion process, recognise its code segments and identify the growing sorted section. Memorising a full implementation is not required.

OCR Exam Reference Language ↔ Python

OCR Exam Reference Language / term	Python	What to remember
`Insertion sort`	`outer loop from index 1`	The first item is treated as an already-sorted section.
`save current item`	`value = values[index]`	Protect the value while other items shift.
`shift larger items right`	`while previous > value`	Make a gap for the saved item.
`insert saved item`	`values[position] = value`	Finish the insertion.

Read both formsIn an examination you may see OCR Exam Reference Language even when you have learned the idea in Python. Translate the structure, not just the symbols.

Worked example

Trace one insertion carefully: the saved value must not be lost while other elements move.

lesson-25-worked.py

values = [3, 7, 10, 5]
value = values[3]
position = 3

while position > 0 and values[position - 1] > value:
    values[position] = values[position - 1]
    position = position - 1

values[position] = value

print(values)

Output

[3, 5, 7, 10]

Work through it line by line

The left section [3, 7, 10] is already sorted.
The next value 5 is saved.
10 shifts right, then 7 shifts right.
3 is not greater than 5, so shifting stops.
5 is inserted into the gap after 3.

Another example

A full sort repeats that insertion process for each remaining item.

lesson-25-example-2.py

values = [5, 1, 4, 2, 3]

for index in range(1, len(values)):
    value = values[index]
    position = index

    while position > 0 and values[position - 1] > value:
        values[position] = values[position - 1]
        position = position - 1

    values[position] = value

print(values)

Output

[1, 2, 3, 4, 5]

Why this example matters

After every outer iteration, the left-hand section up to the current position is sorted.
The while loop shifts only as far as necessary.

Common mistakes

Avoid these errors

Calling adjacent repeated swapping insertion sort; that describes bubble sort more closely.
Forgetting to save the current value before shifting.
Not recognising that the left-hand section is the sorted section.

Exam-safe warningFocus on the pattern: save → shift larger values → insert. OCR does not require you to memorise a full code listing.

Exam-ready checklist

You should now be able to

Apply an insertion step manually.
Identify the sorted section.
Explain why values shift before insertion.
Recognise insertion sort from code/ERL.

What you have learned

Insertion sort grows a sorted section from left to right.
The current value is compared with earlier sorted values.
Larger values shift right to make space.
The current value is inserted into the correct position.