Insertion sort builds a sorted list one element at a time, taking each unsorted item and placing it in the correct position within the already-sorted section. Imagine sorting a hand of playing cards: each new card slides into its right place among the ones you already hold. This intuitive method appears across several GCSE specifications.
How does insertion sort work?
Insertion sort divides the list into two sections: a sorted section on the left (initially just the first element) and an unsorted section on the right. On each pass, it takes the first element from the unsorted section and inserts it into the correct position in the sorted section by comparing and shifting elements.
The key rule: when inserting an element, work backwards through the sorted section, shifting each element one place to the right until you find the correct position.
Worked example: sorting [5, 3, 8, 1, 4]
Pass 1 — insert 3 into sorted section [5]:
The sorted section is [5]. The item to insert is 3.
- Compare 3 with 5: 3 < 5, so shift 5 right.
- 3 goes into position 0.
- List: [3, 5, 8, 1, 4] — sorted section is [3, 5]
Pass 2 — insert 8 into sorted section [3, 5]:
The item to insert is 8.
- Compare 8 with 5: 8 > 5, so 8 stays here. No shifts needed.
- List: [3, 5, 8, 1, 4] — sorted section is [3, 5, 8]
Pass 3 — insert 1 into sorted section [3, 5, 8]:
The item to insert is 1.
- Compare 1 with 8: 1 < 8, shift 8 right.
- Compare 1 with 5: 1 < 5, shift 5 right.
- Compare 1 with 3: 1 < 3, shift 3 right.
- 1 goes into position 0.
- List: [1, 3, 5, 8, 4] — sorted section is [1, 3, 5, 8]
Pass 4 — insert 4 into sorted section [1, 3, 5, 8]:
The item to insert is 4.
- Compare 4 with 8: 4 < 8, shift 8 right.
- Compare 4 with 5: 4 < 5, shift 5 right.
- Compare 4 with 3: 4 > 3, so 4 goes after 3.
- List: [1, 3, 4, 5, 8] — fully sorted ✓
How is insertion sort written in pseudocode?
FOR i ← 1 TO length(list) - 1
key ← list[i]
j ← i - 1
WHILE j >= 0 AND list[j] > key
list[j + 1] ← list[j]
j ← j - 1
ENDWHILE
list[j + 1] ← key
NEXT i
The outer FOR loop steps through each element of the unsorted section. The inner WHILE loop shifts elements right until it finds the correct insertion point for key.
How efficient is insertion sort?
| Scenario | Comparisons | Why |
|---|---|---|
| Best case (already sorted) | O(n) | Inner WHILE loop exits immediately each time — one comparison per pass |
| Worst case (reversed list) | O(n²) | Every element must be shifted past every element already in the sorted section |
| Average case (random order) | O(n²) | On average, each element shifts past half the sorted section |
The best case of O(n) is an important practical advantage: if the data is nearly sorted, insertion sort is far faster than bubble sort or merge sort at detecting it.
Insertion sort vs bubble sort vs merge sort
| Feature | Insertion sort | Bubble sort | Merge sort |
|---|---|---|---|
| Best case | O(n) | O(n) with early termination | O(n log n) — always divides |
| Worst case | O(n²) | O(n²) | O(n log n) |
| Memory | In-place | In-place | Needs extra memory |
| Stable? | Yes | Yes | Yes |
| Good for nearly sorted? | Excellent | Good (with optimisation) | No benefit |
| Intuitive to trace by hand | Yes | Yes | Moderate |
Merge sort wins on large randomly ordered lists; insertion sort wins on small or nearly sorted lists.
When would a programmer choose insertion sort?
Insertion sort is the preferred choice when:
- The list is small (typically fewer than 20–30 items) — the overhead of merge sort's recursion is not worth it.
- The list is nearly sorted — insertion sort identifies sorted runs in linear time.
- The system has very limited memory — no additional arrays are needed.
Many real-world sorting implementations use hybrid algorithms: merge sort for large sublists, switching to insertion sort below a threshold. Python's built-in sorted() function uses a variant called Timsort that does exactly this.
Frequently asked questions
Do I need to know insertion sort for AQA GCSE Computer Science?
AQA GCSE (specification 8525) explicitly requires bubble sort and merge sort as the two sorting algorithms students must understand. Insertion sort is required by Pearson Edexcel's GCSE Computer Science specification. If you are sitting AQA, knowing insertion sort earns you deeper understanding and helps with comparison questions; if you are sitting Edexcel, it is a core requirement. Always check your own exam board specification for the definitive list.
How do I show an insertion sort trace in an exam?
Show the full state of the list after each pass, clearly marking which section is sorted. Highlight the element being inserted and show each comparison and shift. Most mark schemes award separate marks for each correctly completed pass. The most common error is shifting elements in the wrong direction or stopping the inner loop too early — follow the rule: keep shifting left as long as the element being compared is greater than the key.
Is insertion sort stable?
Yes. Insertion sort is stable: when two elements have equal values, their original relative order is preserved. This matters when sorting structured data — for example, sorting a list of students by mark while preserving alphabetical order within the same mark. Because insertion sort only moves an element past those strictly greater than it, equal elements retain their order.
What is the difference between insertion sort and selection sort?
Selection sort finds the smallest remaining element and moves it to the end of the sorted section in one swap per pass. Insertion sort takes the next unsorted element and shifts it into position. Both are O(n²) in the worst case, but insertion sort is typically faster in practice because it does fewer comparisons and swaps on nearly sorted data, and its best case is O(n). Selection sort makes exactly n−1 swaps regardless of the data; insertion sort makes fewer when elements are already close to their final positions.
Professor Turing walks you through insertion sort traces and sorting algorithm comparisons with interactive worked examples at aitutors.me.