What is Merge Sort?
Merge sort is a sorting algorithm that uses a divide and conquer strategy. It works by:
- Splitting the list repeatedly in half until every sub-list has just one element
- Merging pairs of sub-lists back together in sorted order until the whole list is reunited
A list of one element is already sorted — so the magic is all in the merge step.
Worked Example — Sort [8, 3, 5, 1, 6, 2]
Phase 1 — Split
↓ split
↓ split again
↓ split again
Every element is now alone — each is a sorted list of 1.
Phase 2 — Merge (in sorted order)
↑ merge pairs sorted
↑ merge halves sorted
How the Merge Step Works
When merging two sorted sub-lists, compare the first element of each and take the smaller one. Repeat until all elements are placed.
Example: Merge [3, 5, 8] and [1, 2, 6]:
- Compare 3 vs 1 → take 1 → result: [1]
- Compare 3 vs 2 → take 2 → result: [1, 2]
- Compare 3 vs 6 → take 3 → result: [1, 2, 3]
- Compare 5 vs 6 → take 5 → result: [1, 2, 3, 5]
- Compare 8 vs 6 → take 6 → result: [1, 2, 3, 5, 6]
- Remaining: take 8 → result: [1, 2, 3, 5, 6, 8] ✓
AQA Pseudo-code
// Split phase — keep splitting until 1 element
SUBROUTINE mergeSort(list)
IF LEN(list) ≤ 1 THEN
RETURN list // base case: 1 element is already sorted
ENDIF
mid ← LEN(list) DIV 2
left ← mergeSort(list[0:mid]) // recursively sort left half
right ← mergeSort(list[mid:LEN(list)]) // recursively sort right half
RETURN merge(left, right)
ENDSUBROUTINE
// Merge phase — combine two sorted lists
SUBROUTINE merge(left, right)
result ← []
WHILE LEN(left) > 0 AND LEN(right) > 0
IF left[0] ≤ right[0] THEN
APPEND left[0] TO result
REMOVE left[0] FROM left
ELSE
APPEND right[0] TO result
REMOVE right[0] FROM right
ENDIF
ENDWHILE
RETURN result + left + right // append any remaining elements
ENDSUBROUTINE
Efficiency of Merge Sort
| Property | Detail |
|---|
| Time complexity | O(n log n) — far better than bubble sort's O(n²) |
| n = 1,000 items | ~10,000 comparisons (vs ~1,000,000 for bubble sort) |
| n = 1,000,000 items | ~20,000,000 comparisons (vs ~1 trillion for bubble sort) |
| Space complexity | Needs additional memory for the sub-lists during merging |
Bubble Sort vs Merge Sort
| Feature | Bubble Sort | Merge Sort |
|---|
| Time complexity | O(n²) | O(n log n) |
| For n = 1,000 | ~1,000,000 | ~10,000 |
| Memory | In-place (minimal) | Uses extra memory |
| Simplicity | Simpler code | More complex |
| Best for | Small/nearly sorted lists | Large lists where speed matters |
Exam tip: The two phases of merge sort are split (divide) and merge (conquer). Always describe both phases in your answer. The key advantage over bubble sort is that merge sort is O(n log n) — state this explicitly.
⚠️ Common Mistakes
- Only describing the split phase — you must also describe how sorted sub-lists are merged back together
- Confusing merge sort with binary search — they both "halve" but serve completely different purposes
- Forgetting that merge sort uses more memory — it requires additional space for the sub-lists
- Not stating O(n log n) when comparing to bubble sort — this is the key exam point