Python Hub - Master CIE A-Level 9618 Python Programming

15.1 What is Insertion Sort?

Insertion sort builds a sorted region one element at a time. It assumes the first element is already sorted, then takes each subsequent element (the key), compares it with the sorted part to its left, shifts larger elements right to make space, and inserts the key into its correct position.

1. Start with the second element. Assume the first element is already sorted.
2. Compare the key with elements to its left. Find its correct position in the sorted part.
3. Shift larger elements right. Move elements that are greater than key one position to the right.
4. Insert the key. Place it in the correct position. Repeat for all elements.

Example: sort [7, 3, 5, 2]

# Start: [7, 3, 5, 2]  (7 is the sorted region)

# Step 1: key = 3. Compare with 7. 3 < 7, so shift 7 right.
#   [7, 7, 5, 2] -> insert 3 at position 0
#   [3, 7, 5, 2]  sorted part: [3, 7]

# Step 2: key = 5. Compare with 7. 5 < 7, shift 7 right.
#   Compare with 3. 3 < 5, so stop. Insert 5 at position 1.
#   [3, 5, 7, 2]  sorted part: [3, 5, 7]

# Step 3: key = 2. Compare with 7, 5, 3 — all > 2, shift all right.
#   Insert 2 at position 0.
#   [2, 3, 5, 7]  sorted part: [2, 3, 5, 7] — DONE!

Key points:

In-place algorithm: It does not require extra space; sorting happens within the original list.
Best for small data sets: Efficient for small or nearly sorted datasets.
Time complexity: O(n²) worst case, O(n) best case (already sorted).

Knowledge Check 1

How Insertion Sort Works

15.1B Interactive Simulator

Try insertion sort yourself. Change the array values, then click Start. Use Step for manual control or Play for auto-run. Watch the key (amber) being compared with sorted elements (rose), shifted right, and inserted into its correct position.

Interactive Simulator

Array:

Simulation

Status: Click Start to begin.

Code

1for i in range(1, len(arr)):
2    key = arr[i]
3    while j >= 0 and arr[j] > key:
4        arr[j+1] = arr[j]
5        j -= 1
6    arr[j+1] = key

Speed:

15.2 Insertion Sort in Python & Pseudocode

Python

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        # Shift elements greater than key to the right
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key  # Insert key

# Example
arr = [8, 3, 5, 2]
insertion_sort(arr)
print("Sorted array:", arr)
# Output: [2, 3, 5, 8]

Cambridge pseudocode

PROCEDURE InsertionSort(A : ARRAY OF INTEGER)
    FOR i <- 1 TO LENGTH(A) - 1
        key <- A[i]
        j <- i - 1
        WHILE j >= 0 AND A[j] > key DO
            A[j + 1] <- A[j]
            j <- j - 1
        ENDWHILE
        A[j + 1] <- key
    NEXT i
ENDPROCEDURE

Key rules:

The outer loop starts at i = 1 (not 0) — the first element is already sorted.
key = arr[i] saves the value being inserted before shifting overwrites it.
j = i - 1 starts the comparison at the element just left of key.
The while loop shifts elements greater than key one position right.
After the loop, insert key at arr[j + 1] — j has been decremented past the insertion point.

Your Turn — Sort [9, 1, 6, 3]

Sort the list [9, 1, 6, 3] using insertion sort. Show the steps.

Hint:

Step 1: key=1, compare with 9, shift 9 right, insert 1 at 0
Step 2: key=6, compare with 9, shift 9 right, 1<6 so insert 6 at 1
Step 3: key=3, compare with 9,6,1, shift all right, insert 3 at 1

Knowledge Check 2

Python & Pseudocode Implementation

15.3 Tracing Insertion Sort

A trace table for insertion sort tracks: Step, i, key, j, the comparison, and the array after the inner loop. Here is the trace for arr = [8, 3, 5, 2]:

Step	i	key	j	Comparison	Array after inner loop
1	1	3	0	8 > 3, shift 8 right	[3, 8, 5, 2]
2	2	5	1	8 > 5, shift 8 right; 3 < 5, stop	[3, 5, 8, 2]
3	3	2	2→1→0→-1	8>2, 5>2, 3>2, shift all right	[2, 3, 5, 8]

Exam tip:

In a trace, show the full array state after each step (not each individual shift).
The examiner checks that the sorted region grows correctly from left to right.
Each step should show the key, the comparisons made, and the final array state.

Your Turn — Trace [9, 5, 7, 2, 4]

Fill the trace table for arr = [9, 5, 7, 2, 4]. Show each step with i, key, j, and the array after the inner loop.

Hint:

Step 1: i=1, key=5, j=0, 9>5 shift, insert at 0
Step 2: i=2, key=7, j=1, 9>7 shift, 5<7 stop, insert at 1
Step 3: i=3, key=2, shift 9,7,5 right, insert at 0
Step 4: i=4, key=4, shift 9,7,5 right, 2<4 stop, insert at 1

Your Turn — Trace [12, 7, 10, 3, 6, 1, 8]

Fill the trace table for arr = [12, 7, 10, 3, 6, 1, 8]. Show each step.

Hint:

6 steps (i from 1 to 6)
Step 1: key=7, compare with 12, shift 12, insert 7 at 0
Step 2: key=10, compare with 12, shift 12, 7<10 stop, insert at 1
Continue for all 6 steps

Knowledge Check 3

Tracing Insertion Sort

15.4 Performance & Comparison

Scenario	Comparisons	Shifts	Big O
Best case (already sorted)	n - 1	0	O(n)
Worst case (reverse sorted)	~n²/2	~n²/2	O(n²)
Average case	~n²/4	~n²/4	O(n²)

Key rule:

Insertion sort is in-place (O(1) extra space), stable (equal elements keep their relative order), and adaptive (nearly-sorted data runs close to O(n)).
It is preferred for small or nearly-sorted datasets.

Your Turn — Conceptual: Why less efficient on large lists?

Why is insertion sort less efficient on large lists compared to algorithms like merge sort or quick sort?

Hint:

Worst case is O(n²) — comparisons and shifts grow quadratically
Merge sort and quick sort are O(n log n) — much faster for large n
For large datasets, the number of shifts becomes very large

Your Turn — Conceptual: When is insertion sort preferred?

In what scenarios might insertion sort be preferred over more efficient sorting algorithms?

Hint:

Small lists (overhead of complex algorithms is not worth it)
Nearly-sorted data (best case is O(n))
Simple to implement, minimal memory, real-time systems

Knowledge Check 4

Performance & Comparison

15.5 Debugging a Buggy Version

Below is a pseudocode implementation of insertion sort. Each line is numbered. There are four errors that will cause incorrect sorting. Find each one.

01  PROCEDURE InsertionSort(A : ARRAY OF INTEGER)
02      FOR i <- 0 TO LENGTH(A) DO          // ERROR 1
03          key <- A[i]
04          j <- i                            // ERROR 2
05          WHILE j >= 0 AND A[j - 1] < key DO  // ERROR 3
06              A[j] <- A[j + 1]
07              j <- j + 1
08          ENDWHILE
09          A[j + 1] <- key                   // ERROR 4
10      ENDFOR
11  ENDPROCEDURE

Your Turn — Find the 4 errors [4 marks]

Find all four errors in the buggy insertion sort pseudocode. For each: give the line number, explain what is wrong, and write the correction.

Hint:

Line 2: starts at 0, should start at 1
Line 4: j = i, should be j = i - 1
Line 5: uses < (wrong direction), should be >
Line 9: A[j+1] = key, should be A[j] = key (in this buggy context)

Knowledge Check 5

Debugging & Common Errors

15.6 Full Exam-Style Question

(a) — Describe insertion sort [4 marks] Describe how an insertion sort arranges a list of values into ascending order. Do not use code or pseudocode statements.

Your Turn — (a) Model answer

Describe how insertion sort works. Do not use code. [4 marks]

Hint:

Assume the first element is sorted
Take each element (key) and compare with the sorted part to its left
Shift larger elements right to make space
Insert key in its correct position
Repeat for all elements

(b) — Write the code [6 marks] Write a Python function insertion_sort(arr) that sorts the list in ascending order using insertion sort and returns the sorted list.

Your Turn — (b) Model answer

Write insertion_sort(arr) in Python. [6 marks]

Hint:

Outer loop: for i in range(1, len(arr))
key = arr[i], j = i - 1
while j >= 0 and arr[j] > key: shift right
arr[j + 1] = key
Return arr

(c) — Explain performance [2 marks] Explain why insertion sort is faster on nearly-sorted data than on randomly-ordered data.

Your Turn — (c) Model answer

Explain why insertion sort is faster on nearly-sorted data. [2 marks]

Hint:

Nearly-sorted data: few elements out of place
The while loop condition fails quickly (arr[j] < key)
Few shifts needed, so close to O(n)

Knowledge Check 6

Key Points Recap

✓ Key Points Summary

Insertion sort takes each element (key) and inserts it into the sorted part to its left.

The first element is assumed sorted — the outer loop starts at index 1.

The while loop shifts elements greater than key one position right.

After the while loop, key is inserted at position j + 1.

It is an in-place algorithm — O(1) extra space (only key and j).

Python: for i in range(1, len(arr)): key = arr[i]; j = i - 1

Pseudocode: FOR i from 1 to LENGTH(A) - 1; key = A[i]; j = i - 1

While loop: while j >= 0 and arr[j] > key: shift right, j -= 1

After loop: arr[j + 1] = key (j has been decremented past the insertion point).

For descending order: change > to < in the while condition.

Trace table: track Step, i, key, j, comparison, and array state after each step.

Each step extends the sorted region by one element (left to right).

Big O: O(n²) worst case (reverse sorted), O(n) best case (already sorted).

Insertion sort is adaptive — nearly-sorted data runs close to O(n).

Preferred for small lists, nearly-sorted data, and online (streaming) sorting.

Four common bugs: start at 0 (should be 1), j=i (should be i-1), < (should be >), wrong insertion position.

15.7 Practice Tasks

Fifteen exam-style insertion sort tasks. Each shows only the question — click Hint for the thought process, or Help for the worked solution.

Exam tip:

For every insertion sort task, the marker checks: (1) outer loop starts at 1 (not 0), (2) key is saved before shifting, (3) while loop shifts elements > key right (not swaps), (4) key is inserted at j+1 after the loop.
The most common mark loss is starting the loop at 0 instead of 1.

1Practice Task — Standard insertion sort [5 marks]

Write a Python function insertion_sort(arr) that sorts a list in ascending order and returns it.

2Practice Task — Sort [8, 3, 5, 2] [4 marks]

Sort [8, 3, 5, 2] using insertion sort. Show each step with key, comparisons, and the array after each insertion.

3Practice Task — Descending order [4 marks]

Write a function insertion_sort_desc(arr) that sorts in DESCENDING order (largest first).

4Practice Task — Trace [9, 5, 7, 2, 4] [5 marks]

Trace insertion sort on [9, 5, 7, 2, 4]. Show each step: i, key, j, array after inner loop.

5Practice Task — Pseudocode implementation [6 marks]

Write Cambridge pseudocode for InsertionSort(A) that sorts array A in ascending order.

6Practice Task — Describe in prose [4 marks]

Describe how insertion sort arranges data into ascending order. Do not use code or pseudocode.

7Practice Task — Big O [2 marks]

What is the Big O of insertion sort (worst case), and why?

8Practice Task — Best case [2 marks]

What is the best case for insertion sort, and what is its Big O?

9Practice Task — Find 4 bugs [4 marks]

The buggy pseudocode has 4 errors: line 2 starts at 0, line 4 has j=i, line 5 uses < instead of >, line 9 uses j+1. Give the correction for each.

10Practice Task — Why start at 1? [2 marks]

Explain why the outer loop starts at index 1, not index 0.

11Practice Task — Why j = i - 1? [2 marks]

Explain why j is set to i - 1, not i.

12Practice Task — Insertion vs bubble [2 marks]

Give one advantage of insertion sort over bubble sort.

13Practice Task — In-place [2 marks]

Explain what it means for insertion sort to be an "in-place" algorithm.

14Practice Task — Count comparisons [3 marks]

How many comparisons does insertion sort make on [8, 3, 5, 2] (worst case)? Show your working.

15Practice Task — Full exam question [12 marks]

(a) Describe insertion sort in prose [4]. (b) Write insertion_sort(arr) in Python [6]. (c) Explain why it is faster on nearly-sorted data [2].

Question Bank

Answer all questions, then press Submit Quiz to see your score.

0/12 answered

Question 1Multiple Choice

What is the key idea of insertion sort?

Question 2True / False

The outer loop starts from index 1 because index 0 is already sorted.

Question 3Multiple Choice

What does the while loop do?

Question 4Multiple Choice

Where is key inserted after the while loop?

Question 5True / False

Insertion sort is an in-place algorithm.

Question 6Multiple Choice

What is the worst-case Big O?

Question 7Multiple Choice

What is the best case?

Question 8True / False

Insertion sort is preferred for small or nearly-sorted datasets.

Question 9Multiple Choice

In the pseudocode, the outer loop is:

Question 10Multiple Choice

What is the while loop condition?

Question 11True / False

For descending order, change > to < in the while condition.

Question 12Multiple Choice

Both bubble sort and insertion sort are O(n²). Which is faster on nearly-sorted data?

Answer all 12 questions to enable submission.