Insertion sort builds a sorted section at the start of the list, one element at a time. It takes each element (the key), compares it with elements in the sorted section, and inserts it in the correct position by shifting larger elements right.
Analogy: Like sorting playing cards in your hand — pick each card and slot it into the right position among the cards already held.
How Insertion Sort Works — [5, 2, 8, 1, 4]
🟩 Green = sorted section 🟨 Yellow = key being inserted 🟪 Purple = just inserted
Start:
5
2
8
1
4
Pass 1 — key = 2 (index 1):
Key = 2:
5
2
8
1
4
2 < 5 → shift 5:
2
5
8
1
4
Pass 2 — key = 8 (index 2):
Key = 8:
2
5
8
1
4
8 > 5 → ok:
2
5
8
1
4
Pass 3 — key = 1 (index 3):
Key = 1:
2
5
8
1
4
1 < 8,5,2 → shift all:
1
2
5
8
4
Pass 4 — key = 4 (index 4):
Key = 4:
1
2
5
8
4
4 < 8,5; 4 > 2:
1
2
4
5
8
Final sorted: [1, 2, 4, 5, 8] ✓
Pseudocode
// Insertion sort — ascending order
n = length(list)
FOR i = 1 TO n - 1
key = list[i]
j = i - 1
WHILE j >= 0 AND list[j] > key
list[j+1] = list[j] // Shift element right
j = j - 1
END WHILE
list[j+1] = key // Insert key in correct positionEND FOR
Key Properties
Property
Value
Time complexity (worst)
O(n²) — reverse sorted list
Time complexity (best)
O(n) — already sorted list (no shifts needed)
In-place?
Yes — sorts within the original array
Stable sort?
Yes
Good for
Small or nearly-sorted lists
The "key"
The current element being inserted
Comparison: Insertion Sort vs Bubble Sort vs Merge Sort
Feature
Insertion Sort
Bubble Sort
Merge Sort
Worst case
O(n²)
O(n²)
O(n log n)
Best case
O(n)
O(n) optimised
O(n log n)
In-place
Yes
Yes
No
Good for nearly sorted?
✓ Very good
✓ Good (optimised)
— No benefit
Simple to implement?
Yes
Yes
More complex
Exam tip: In insertion sort trace questions, identify the key (current element), then show each shift right as larger sorted elements are moved to make space. The key is inserted at the first position where it's greater than or equal to its left neighbour. Remember: insertion sort starts at index 1 (index 0 is already a "sorted section" of one). Best case is O(n) for an already-sorted list — no shifts required at any pass.
⚠️ Common Mistakes
Starting at index 0 — insertion sort starts at index 1 (the first element to insert)
Forgetting to shift elements right before inserting — do not overwrite without shifting
Saying the best case is O(n²) — for an already-sorted list, the inner WHILE never executes, giving O(n)
✅ Notes completed!
▶
Video coming soon
Click slide or press arrow keys to navigate
Worksheet — 2.1.3c Insertion Sort
8 questions · 20 marks
Q1Describe how insertion sort works.[2]
✅ Mark scheme
Each element (key) is taken in turn [1] and compared with elements in the already-sorted section to its left, with larger elements shifted right until the correct position is found and the key is inserted [1].
Q2Perform insertion sort on [6, 3, 9, 2, 5]. Show every pass.[5]
The current element being taken from the unsorted section and inserted into the correct position in the sorted section [1].
Q4State the best-case and worst-case time complexity of insertion sort and describe when each occurs.[4]
✅ Mark scheme
Best case: O(n) [1] — when the list is already sorted, the inner WHILE loop never executes as each key is already in the correct position [1]. Worst case: O(n²) [1] — when the list is in reverse order, each key must be shifted all the way to position 0 [1].
Q5Is insertion sort in-place? Explain your answer.[2]
✅ Mark scheme
Yes [1] — insertion sort sorts within the original array using only a single variable (key) to temporarily hold the current element. No new array is created [1].
Q6In pass 3 of insertion sort on [3, 6, 9, 2, 5] (key=2): describe exactly what happens.[3]
✅ Mark scheme
key = 2 is stored [1]; compare 2 with 9 → 9>2, shift 9 right; compare 2 with 6 → 6>2, shift 6 right; compare 2 with 3 → 3>2, shift 3 right [1]; insert 2 at index 0. List becomes [2,3,6,9,5] [1].
Q7Give one advantage of insertion sort over merge sort.[1]
✅ Mark scheme
Any one: insertion sort is in-place (less memory) [1]; simpler to implement [1]; more efficient than merge sort for small or nearly-sorted lists [1].
Q8Why does insertion sort start at index 1, not index 0?[2]
✅ Mark scheme
Index 0 is already a sorted section of one element [1] — a single element has nothing to compare with, so it is trivially sorted. The algorithm begins by taking index 1 as the first key to insert [1].
?
out of 20 — self-mark above
Topic Quiz
Question 1 of 15
You scored
out of 15
Card 1 of 8
Click to reveal definition
🎉
Complete!
Term
Definition
🎯
Mini Test — 2.1.3c Insertion Sort
10 questions · 10 marks · 10 minutes
⏱ 10:00
10 marks
Section A — Multiple Choice [5 marks]
Q1What does insertion sort do with each element?
Q2What is the best-case time complexity of insertion sort?
Q3Insertion sort on [4, 1, 7, 2]. After pass 1 (key=1), what is the list?
Q4Is insertion sort an in-place algorithm?
Q5When does insertion sort achieve O(n) time?
Section B — Short Answer [5 marks]
Q6Describe insertion sort using the analogy of sorting playing cards.
Mark schemeYou pick up each card one at a time [1] and insert it into the correct position among the cards already held in sorted order in your hand, shuffling other cards along to make room [1].
Q7For [7, 3, 5, 1], trace pass 1 of insertion sort (key = 3) in full.
Mark schemekey = list[1] = 3 [1]; compare 3 with list[0]=7 → 7>3, shift 7 right → list becomes [7,7,5,1]; insert key 3 at index 0 → [3,7,5,1] [1]. Result after pass 1: [3,7,5,1].
Q8Explain why a nearly-sorted list is better suited to insertion sort than bubble sort.
Mark schemeIn insertion sort, if an element is already near its correct position, the inner loop does very little work (few or no shifts) [1]. A nearly-sorted list means most keys need 0–1 shifts, giving close to O(n) performance [1].
Q9State two similarities between insertion sort and bubble sort.
Mark schemeAny two: both are O(n²) worst case [1]; both are in-place [1]; both are simple to implement [1]; both can achieve O(n) best case (optimised/already sorted) [1].
Q10Why is insertion sort not suitable for sorting large datasets compared to merge sort?
Mark schemeInsertion sort is O(n²) worst case while merge sort is O(n log n) [1]. For large n, insertion sort performs far more operations — e.g. for 10,000 items: ~100 million operations vs ~130,000 [1].