Merge sort works by relentlessly dividing a list in half — right down to single-element sublists — then rebuilding it by merging pairs of sublists in sorted order. Every merge is a careful comparison, and the result is a fully sorted list built from the ground up, step by disciplined step.
What is the divide-and-conquer principle?
Merge sort is a classic example of the divide-and-conquer strategy: split a problem into smaller sub-problems of the same type, solve each independently, then combine the results. Think of it like sorting a hand of playing cards by giving half to a friend, asking you both to sort your halves separately, then combining them by holding both sorted halves face-up and always picking the smaller top card.
The key insight is that merging two already-sorted lists is far easier and faster than sorting one unsorted list from scratch.
How does merge sort work? Step-by-step
Starting list: [38, 27, 43, 3]
Step 1 — Divide
Split the list repeatedly until every sublist has one element (a list of one is always sorted):
[38, 27, 43, 3]
↙ ↘
[38, 27] [43, 3]
↙ ↘ ↙ ↘
[38] [27] [43] [3]
Step 2 — Merge (left pair)
Compare [38] and [27]: 27 < 38, so pick 27 first. Result: [27, 38].
Step 3 — Merge (right pair)
Compare [43] and [3]: 3 < 43, so pick 3 first. Result: [3, 43].
Step 4 — Final merge
Merge [27, 38] and [3, 43]:
| Step | Left pointer | Right pointer | Pick | Output so far |
|---|---|---|---|---|
| 1 | 27 | 3 | 3 | [3] |
| 2 | 27 | 43 | 27 | [3, 27] |
| 3 | 38 | 43 | 38 | [3, 27, 38] |
| 4 | — | 43 | 43 | [3, 27, 38, 43] |
Final sorted list: [3, 27, 38, 43] ✓
How is the merge step written in pseudocode?
FUNCTION merge(left, right)
result ← []
WHILE left is not empty AND right is not empty
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
END IF
END WHILE
APPEND remaining elements of left TO result
APPEND remaining elements of right TO result
RETURN result
END FUNCTION
The two "append remaining" lines handle the case where one half is exhausted before the other — the leftover elements are already in order, so they can all be appended directly.
What is merge sort's time complexity?
The splitting phase divides n items into single elements in log₂ n steps. At each level, the merging work touches every element once — that is n operations per level. Multiply them together and you get O(n log n).
| Case | Time complexity | Why |
|---|---|---|
| Best case | O(n log n) | Dividing always takes log n levels |
| Average case | O(n log n) | Merge work at each level is always O(n) |
| Worst case | O(n log n) | Unlike quicksort, merge sort is always consistent |
Merge sort is one of the few algorithms that guarantees O(n log n) in all cases. Its weakness is space: it requires O(n) extra memory for the temporary sublists, unlike bubble sort which sorts in-place using O(1) extra space.
How does merge sort compare with bubble and insertion sort?
| Algorithm | Worst-case time | Extra space | Stable? | Consistent? |
|---|---|---|---|---|
| Bubble sort | O(n²) | O(1) | Yes | Yes |
| Insertion sort | O(n²) | O(1) | Yes | Yes |
| Merge sort | O(n log n) | O(n) | Yes | Yes (always O(n log n)) |
| Quicksort | O(n²) worst | O(log n) | No | No |
For large datasets, merge sort is dramatically more efficient than bubble or insertion sort. A list of 1,000,000 items requires roughly a trillion operations under O(n²) but only around 20 million under O(n log n).
Why is merge sort used in real software?
Merge sort's guaranteed O(n log n) and stability make it the algorithm of choice when either of those properties is non-negotiable. Python's built-in sorted() function uses Timsort — a hybrid of merge sort and insertion sort. Java's Arrays.sort() for objects uses a dual-pivot quicksort for primitives and merge sort logic for objects (because objects need stability). Understanding merge sort is therefore not just examination preparation — it underpins production software used by millions of people daily.
Frequently asked questions
Why does merge sort need O(n) extra space?
During the merge step, you cannot rearrange the original list in place — you need a temporary list to hold the merged output. If you tried to overwrite the input list while reading it, you would corrupt the values you had not yet compared. Some advanced in-place variants of merge sort exist, but they are far more complex and are well beyond GCSE scope.
How do I trace merge sort in an exam?
Draw the splitting tree first (work downwards until every sublist has one element), then merge from the bottom up (work upwards, combining pairs). Show each merge step as a table comparing the front elements of both sublists. Most mark schemes award separate marks for the correct split tree and the correct merge steps.
Is merge sort recursive?
Yes — the standard implementation calls itself on each half, making it a recursive algorithm. The base case is a list of zero or one elements, which is already sorted and returned directly without further recursive calls. If your teacher has covered recursion, understanding merge sort's recursive structure helps make both topics click simultaneously.
Which GCSE specifications require knowledge of merge sort?
AQA GCSE Computer Science (8525) expects students to understand and trace merge sort. OCR J277 also covers it. Edexcel includes it within broader coverage of sorting algorithms. In all cases, you should be able to describe the divide phase, the merge phase, and the O(n log n) time complexity, and compare it with bubble sort and insertion sort.
Work through merge sort step by step with interactive examples — Professor Turing at aitutors.me will trace every comparison with you.