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]