Merge sort is a divide-and-conquer algorithm. It works by recursively splitting the list in half until each sub-list has just one item (which is trivially sorted), then merging the sub-lists back together in the correct order.
Step 1: Divide — split list into two halves. Repeat until all sub-lists have length 1
Step 2: Merge — compare first items of each sub-list; always pick the smaller one first
Step 3: Repeat — keep merging sorted sub-lists until the full list is reconstructed
Worked Example
Sorting: [5, 3, 8, 1]
[5, 3, 8, 1]
[5, 3]
[8, 1]
[5] [3]
[8] [1]
Merge → [3, 5]
Merge → [1, 8]
Merge → [1, 3, 5, 8] ✓
Merge Sort vs Bubble Sort
Why Merge Sort is Better for Large Data
Merge sort: O(n log n) — efficient even for very large lists. Always takes the same number of steps regardless of the initial order.
Bubble sort: O(n²) worst case — slow for large data. Simple to code but impractical for large datasets.
Merge sort needs more memory — creates extra lists during the split/merge stages
Bubble sort uses less memory — sorts in place, no extra lists needed
Exam Practice
Have a go at this question
Edexcel-style question
Explain why merge sort is considered more efficient than bubble sort for sorting large lists.
3 marks
Merge sort has O(n log n) time complexity [1], whereas bubble sort has O(n²) worst-case complexity [1]. This means for large lists, merge sort performs significantly fewer comparisons and completes much faster [1].
Key Takeaways
What to Remember
Merge sort: split into halves → sort each half → merge in order
O(n log n) — efficient; suitable for large datasets
Uses more memory than bubble sort — creates sub-lists during splitting
Always consistent — same performance regardless of initial list order