Insertion Sort Algorithm

This lesson covers the insertion sort algorithm as required by OCR J277 Section 2.2. Insertion sort is the third standard sorting algorithm you must know for the OCR GCSE Computer Science exam. It is an intuitive algorithm that works similarly to how most people sort playing cards in their hand.

---

What Is Insertion Sort?

Insertion sort is a sorting algorithm that builds a sorted section of the list one element at a time. It works by taking each element from the unsorted portion and inserting it into its correct position within the sorted portion.

Imagine you are holding a hand of playing cards. You pick up one card at a time and slide it into the correct position among the cards you have already sorted.

---

How Insertion Sort Works

1. Start with the second element (index 1) — the first element is considered "sorted" on its own.
2. Compare it with the elements in the sorted portion (to its left).
3. Shift any sorted elements that are greater than the current element one position to the right.
4. Insert the current element into its correct position.
5. Move to the next unsorted element and repeat.
6. Continue until all elements have been inserted into the sorted portion.

---

Insertion Sort in OCR Pseudocode

procedure insertionSort(list)
    for i = 1 to list.length - 1
        current = list[i]
        j = i - 1

        while j >= 0 AND list[j] > current
            list[j + 1] = list[j]
            j = j - 1
        endwhile

        list[j + 1] = current
    next i
endprocedure

Insertion Sort in Python

def insertion_sort(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

    return lst

numbers = [5, 3, 8, 1, 2]
print(insertion_sort(numbers))  # Output: [1, 2, 3, 5, 8]

OCR Exam Tip: When tracing insertion sort, clearly show which element is being inserted and where it ends up. The examiner wants to see that you understand the element is being placed into its correct position within the already-sorted portion of the list.

---

Tracing Through Insertion Sort

Let us sort the list [5, 3, 8, 1, 2]:

Initial list: [5, 3, 8, 1, 2]

Step	Current Element	Sorted Portion (before)	Action	List After Insertion
1	3 (index 1)	[5]	3 < 5, shift 5 right, insert 3	[3, 5, 8, 1, 2]
2	8 (index 2)	[3, 5]	8 > 5, no shift needed, stays in place	[3, 5, 8, 1, 2]
3	1 (index 3)	[3, 5, 8]	1 < 8, 1 < 5, 1 < 3, shift all right, insert 1 at start	[1, 3, 5, 8, 2]
4	2 (index 4)	[1, 3, 5, 8]	2 < 8, 2 < 5, 2 < 3, 2 > 1, insert after 1	[1, 2, 3, 5, 8]

Final sorted list: [1, 2, 3, 5, 8]

---

Properties of Insertion Sort

Property	Detail
Best case	O(n) — data is already sorted (only one comparison per element)
Worst case	O(n²) — data is in reverse order
Average case	O(n²)
Space complexity	O(1) — sorts in place
Stability	Stable — equal elements maintain their relative order
Adaptive	Yes — very efficient on nearly-sorted data

---

When Is Insertion Sort Useful?

Insertion sort is a good choice when:

• The dataset is small — the simplicity of the algorithm is advantageous.
• The data is nearly sorted — insertion sort runs in nearly O(n) time because few shifts are needed.
• You want an algorithm that is easy to implement and understand.
• You need a stable sort that preserves the order of equal elements.

Insertion sort is a poor choice when:

• The dataset is large — O(n²) becomes very slow.
• The data is in random or reverse order — maximum number of shifts needed.

---

Comparing Insertion Sort with Bubble Sort

Feature	Bubble Sort	Insertion Sort
Mechanism	Compares and swaps adjacent elements	Inserts each element into its correct position
Best case	O(n) with swapped flag	O(n) on nearly sorted data
Worst case	O(n²)	O(n²)
Number of swaps	Generally more swaps	Generally fewer data movements
Practical speed	Usually slower in practice	Usually faster in practice
Stability	Stable	Stable

---

Summary

• Insertion sort builds a sorted portion one element at a time.
• Each element is inserted into its correct position within the sorted section.
• Best case is O(n) for nearly sorted data; worst case is O(n²).
• It sorts in place (O(1) space) and is stable.
• It is efficient for small datasets and nearly-sorted data.

OCR Exam Tip: Insertion sort is the algorithm OCR students most often struggle to describe. The key phrase is: "each element is taken in turn and inserted into its correct position in the sorted part of the list." Practise writing this description until it is automatic.

---

Detailed Trace of a Single Insertion

Let us focus on one step in detail. Say we are sorting [3, 5, 8, **1**, 2] and the "current" element is 1 at index 3. The sorted portion is [3, 5, 8].

Sub-step	j	list[j]	Comparison	Action	List State
Start	2	8	1 < 8? Yes	Shift 8 right: list[3] = 8	[3, 5, 8, 8, 2]
Decrement j	1	5	1 < 5? Yes	Shift 5 right: list[2] = 5	[3, 5, 5, 8, 2]
Decrement j	0	3	1 < 3? Yes	Shift 3 right: list[1] = 3	[3, 3, 5, 8, 2]
Decrement j	-1	—	j >= 0 false	Insert current (1) at list[0]	[1, 3, 5, 8, 2]

Notice how the inner loop shifts values to the right until it finds the correct position for current. This shifting is why insertion sort is O(n²) in the worst case — each element may require up to n shifts.

---

Best-Case Trace: Already Sorted Data

Sort the already-sorted list [1, 2, 3, 4, 5]:

i	current	Inner loop runs?	List After
1	2	No (2 > 1)	[1, 2, 3, 4, 5]
2	3	No (3 > 2)	[1, 2, 3, 4, 5]
3	4	No (4 > 3)	[1, 2, 3, 4, 5]
4	5	No (5 > 4)	[1, 2, 3, 4, 5]

Only 4 comparisons, no shifts — best case O(n). This is why insertion sort is fast on nearly-sorted data.

---

Worst-Case Trace: Reverse-Sorted Data

Sort [5, 4, 3, 2, 1]: