What is Merge Sort?
Merge sort is a more efficient sorting algorithm than bubble sort. It uses a divide and conquer strategy — it splits the list into halves, sorts each half recursively, then merges the sorted halves back together.
The two phases of merge sort
- Split phase: repeatedly divide the list in half until you have individual elements (a single element is by definition "sorted")
- Merge phase: repeatedly combine pairs of sorted sub-lists into a larger sorted list by comparing elements and taking the smaller one first
Step-by-step example — sorting: 8, 3, 5, 1, 9, 2
Split 1 — divide in half
835
192
Split 2 — divide again
8
35
1
92
Split 3 — individual elements
8
3
5
1
9
2
Merge 1 — merge pairs (compare and take smaller first)
38
35
1
29
8+3→[3,8] | 5 stays | 1 stays | 9+2→[2,9]
Merge 2 — merge sub-lists
358
129
Final merge — sorted!
123589
The merge step in detail
When merging two sorted sub-lists, you compare the first element of each sub-list and take the smaller one into the result. You repeat until one sub-list is empty, then append the remainder of the other.
Example: merging [3, 5, 8] and [1, 2, 9]:
- Compare 3 and 1 → take 1
- Compare 3 and 2 → take 2
- Compare 3 and 9 → take 3
- Compare 5 and 9 → take 5
- Compare 8 and 9 → take 8
- Take remaining: 9
- Result: [1, 2, 3, 5, 8, 9] ✓
Merge Sort vs Bubble Sort
| Bubble Sort | Merge Sort |
|---|
| Strategy | Repeatedly swap adjacent pairs | Divide and conquer |
| Efficiency | Less efficient for large data | More efficient for large data |
| Extra memory | In-place (only temp var) | Needs extra memory for sub-lists |
| Complexity | Simpler to understand and code | More complex |
Exam tip: For IGCSE, you need to be able to describe merge sort (split until individual elements, then merge back in order) and show the stages of a merge sort on a given list. You do not need to write pseudocode for merge sort. The key advantage over bubble sort is that it is more efficient for large datasets.
⚠️ Common Mistakes
- Confusing the split phase with the merge phase — be clear which one you are showing
- Not continuing to split until all sub-lists are size 1 before starting to merge
- During the merge step, not picking the SMALLER element first when comparing
- Saying merge sort uses no extra memory — it does need temporary storage for the merged sub-lists