1.1h Merge sort — Edexcel 4CP0

What is Merge Sort?

Merge sort is an efficient sorting algorithm based on the divide and conquer principle. It works by recursively splitting the list in half until each sub-list contains only one element (which is trivially sorted), then merging the sub-lists back together in the correct order.

How Merge Sort Works — The Two Phases

Phase 1: Divide (Split)

Take the list and find the midpoint
Split into two halves
Repeat for each half until every sub-list has only 1 element

Phase 2: Conquer (Merge)

Take two sorted sub-lists and merge them into one sorted list
Compare the first element of each sub-list; take the smaller one
Repeat until one sub-list is empty; append the remaining elements
Repeat the merge process up the tree until the full list is reconstructed

Worked Example

Sort: [38, 27, 43, 3, 9, 82, 10]

Split phase:

[38, 27, 43, 3, 9, 82, 10]
[38, 27, 43] and [3, 9, 82, 10]
[38] [27, 43] and [3, 9] [82, 10]
[38] [27] [43] and [3] [9] [82] [10]

Merge phase:

[27, 38] [43] → [27, 38, 43] and [3, 9] [10, 82] → [3, 9, 10, 82]
[27, 38, 43] + [3, 9, 10, 82] → [3, 9, 10, 27, 38, 43, 82]

Comparison: Merge Sort vs Bubble Sort

Feature	Bubble Sort	Merge Sort
Time complexity (worst)	O(n²)	O(n log n)
Method	Compare adjacent pairs and swap	Divide, then merge sorted halves
Suitable for large lists	No — too slow	Yes — much more efficient
Memory usage	In-place (no extra memory)	Requires extra memory for sub-lists
Simplicity	Simple to implement	More complex to implement

📝 Exam Tip: In Paper 1, you may be asked to show the state of the list at each stage of merge sort — both the split phase (tree diagram) and the merge phase. Practice drawing the split tree clearly.

⚠️ Common Mistakes

Forgetting that merge sort has two distinct phases: splitting AND merging
Merging incorrectly — always compare the front elements of each sub-list and take the smaller
Saying merge sort is O(n²) — it is O(n log n), which makes it much more efficient than bubble sort for large datasets