Merge sort is a divide and conquer sorting algorithm. It works in two phases:
Divide: Repeatedly split the list in half until every sub-list has just one element (a single element is always sorted).
Merge (conquer): Repeatedly merge pairs of sorted sub-lists back together in sorted order until one fully sorted list remains.
Merge sort is much more efficient than bubble sort for large datasets because it has a time complexity of O(n log n).
Worked Example — [38, 27, 43, 3, 9, 82, 10]
DIVIDE PHASE — split until single elements:
[38, 27, 43, 3, 9, 82, 10]
↓ split
[38, 27, 43]
[3, 9, 82, 10]
↓ split
[38]
[27, 43]
[3, 9]
[82, 10]
↓ split
[38]
[27]
[43]
[3]
[9]
[82]
[10]
MERGE PHASE — merge pairs in sorted order:
↑ merge sibling pairs
[27, 43]
[38]
[3, 9]
[10, 82]
↑ merge
[27, 38, 43]
[3, 9, 10, 82]
↑ final merge
[3, 9, 10, 27, 38, 43, 82] ✓
How the Merge Step Works
When merging two sorted sub-lists, compare the front element of each. Take the smaller one, add it to the result, then repeat until both sub-lists are empty.
Example: Final merge — [27, 38, 43] and [3, 9, 10, 82]:
Step
Left pointer
Right pointer
Result so far
1
27
3
[3] — take 3 (smaller)
2
27
9
[3, 9] — take 9 (smaller)
3
27
10
[3, 9, 10] — take 10 (smaller)
4
27
82
[3, 9, 10, 27] — take 27 (smaller)
5
38
82
[3, 9, 10, 27, 38] — take 38 (smaller)
6
43
82
[3, 9, 10, 27, 38, 43] — take 43 (smaller)
7
(empty)
82
[3, 9, 10, 27, 38, 43, 82] — append remaining
Pseudocode
// Merge sort — divides and mergesFUNCTION mergeSort(list)
IF length(list) <= 1 THENRETURN list // Base case: already sortedEND IF
mid = length(list) DIV 2
left = mergeSort(list[0..mid-1]) // Recursively sort left half
right = mergeSort(list[mid..end]) // Recursively sort right halfRETURN merge(left, right)
FUNCTION merge(left, right)
result = []
WHILE length(left) > 0 AND length(right) > 0
IF left[0] <= right[0] THEN
result.append(left[0])
left = left[1..]
ELSE
result.append(right[0])
right = right[1..]
END IFEND WHILERETURN result + left + right // Append any remaining elementsEND FUNCTION
Key Properties of Merge Sort
Property
Value
Time complexity
O(n log n) — all cases (best, average, worst)
Space complexity
O(n) — requires additional memory for sub-lists
Technique
Divide and conquer + recursion
In-place?
No — creates new lists during splitting/merging
Presort required?
No
Stable sort?
Yes — maintains relative order of equal elements
Merge Sort vs Bubble Sort
Feature
Merge Sort
Bubble Sort
Time complexity
O(n log n)
O(n²)
Speed for large n
Much faster
Much slower
Memory usage
Extra O(n) memory needed
In-place — O(1) extra
Implementation
More complex (recursive)
Simple
Best for
Large datasets
Small / teaching
Exam tip: In a merge sort trace question, show the divide phase as a tree diagram (splitting in half each time), then show the merge phase building up sorted sub-lists. Remember: merge sort uses O(n log n) time complexity — contrast this with bubble sort's O(n²). The key disadvantage of merge sort is that it needs extra memory — it is NOT in-place. Mention "divide and conquer" and "recursion" in description questions.
⚠️ Common Mistakes
Saying merge sort is in-place — it is NOT; it requires extra memory for sub-lists
Forgetting to show the merge phase — you must show how sorted sub-lists are combined
Getting the split wrong — always split into roughly equal halves (use integer division)
Not continuing the merge phase to completion — work all the way up to the final merged list
Confusing merge sort's complexity — it's O(n log n), not O(n²) like bubble sort
✅ Notes completed!
▶
Video coming soon
Click slide or press arrow keys to navigate
Worksheet — 2.1.3b Merge Sort
8 questions · 18 marks
Q1Describe the two phases of merge sort.[2]
✅ Mark scheme
Divide phase: the list is repeatedly split in half until individual single-element lists remain [1]. Merge phase: adjacent sub-lists are merged back together in sorted order until one fully sorted list is produced [1].
Q2Show the divide phase of merge sort on [8, 3, 5, 1, 7, 2].[3]
Q4State the time complexity of merge sort and explain what this means.[2]
✅ Mark scheme
O(n log n) [1] — the time taken grows as n multiplied by log n, making it much more efficient than O(n²) for large lists [1].
Q5Explain what "divide and conquer" means in the context of merge sort.[2]
✅ Mark scheme
Divide and conquer means breaking the problem into smaller sub-problems [1], solving each sub-problem (sorting individual elements/pairs), then combining the solutions back together to solve the original problem [1].
Q6Is merge sort an in-place sorting algorithm? Explain your answer.[2]
✅ Mark scheme
No [1] — merge sort requires additional memory to store the sub-lists created during the divide phase and the temporary merged lists during the merge phase. It is not sorted within the original array [1].
Q7Give two advantages of merge sort over bubble sort.[2]
✅ Mark scheme
Any two: much faster — O(n log n) vs O(n²) [1]; more efficient for large datasets [1]; performance doesn't degrade as badly with large n [1].
Q8Explain why a single-element list is considered already sorted in merge sort.[1]
✅ Mark scheme
A list of one element has nothing to compare — it is trivially sorted by definition. This is the base case that stops the recursive splitting [1].
?
out of 18 — self-mark above
Topic Quiz
Question 1 of 15
You scored
out of 15
Card 1 of 10
Click to reveal definition
🎉
Complete!
Term
Definition
🎯
Mini Test — 2.1.3b Merge Sort
10 questions · 10 marks · 10 minutes
⏱ 10:00
10 marks
Section A — Multiple Choice [5 marks]
Q1What technique does merge sort use?
Q2What is the time complexity of merge sort?
Q3Is merge sort an in-place sorting algorithm?
Q4What is the base case for the divide phase of merge sort?
Q5When merging [2, 5, 9] and [1, 4, 7], what is the first element of the result?
Section B — Short Answer [5 marks]
Q6Describe the divide phase of merge sort.
Mark schemeThe list is repeatedly split into two halves [1] until every sub-list contains only a single element (base case) [1]. A single-element list is considered already sorted.
Q7Explain one advantage and one disadvantage of merge sort compared to bubble sort.
Mark schemeAdvantage: much faster — O(n log n) vs O(n²) for bubble sort [1]. Disadvantage: requires more memory — not in-place, needs extra space for sub-lists [1].
Q8Show the first split of merge sort on [6, 2, 9, 4, 1, 8].
Mark scheme[6, 2, 9] and [4, 1, 8] [1] — split at the midpoint (index 3 of 6).
Q9When merging two sorted lists [3, 8] and [1, 5], show the complete merge process step by step.
Mark schemeCompare 3 and 1 → take 1 (result: [1]) [1]; compare 3 and 5 → take 3 (result: [1, 3]) [1]; compare 8 and 5 → take 5 (result: [1, 3, 5]) [1]; append remaining 8 (result: [1, 3, 5, 8]) [1]. Award 1 mark for each correct comparison/take step.
Q10Why is merge sort preferred over bubble sort for large datasets?
Mark schemeMerge sort is O(n log n) while bubble sort is O(n²) [1] — for large n, this difference is enormous (e.g. 1 million items: ~20 million ops for merge sort vs ~1 trillion for bubble sort) [1].