Merge Sort
Master Merge Sort for GCSE Computer Science with this free worksheet and full mark scheme — Foundation and Higher exam-style questions with worked answers. A merge sort splits a list into single items, then repeatedly merges them back together in order.
Free downloads
These worksheets and mark schemes are original, written for Virtus Academy and checked against the current AQA specification. Every worksheet comes with a full mark scheme.
Topic overview
A merge sort uses divide and conquer: it splits the list into single items, then merges them back together in order.
The splitting phase repeatedly halves the list until every sublist contains just one item. A list of one item is already sorted, which is why the splitting stops there.
The merging phase then combines pairs of sublists. Compare the first item of each and take the smaller, repeating until one sublist is empty, then append the rest of the other. Merging continues, doubling the sublist size each time, until a single sorted list remains. Merge sort is far more efficient than bubble sort on large lists, but needs extra memory to hold the sublists.
Revision notes
The splitting phase
Repeatedly halve the list until every sublist contains one item.
A one-item list is already sorted by definition, which is why the splitting stops at that point. A list of 8 items splits into 4, then 2, then 1.
The merging phase
Take two sublists. Compare their first items and move the smaller into the merged list.
Repeat until one sublist is empty, then append everything remaining in the other. This produces a sorted list twice the size. Continue until one list remains.
Efficiency and memory
Far more efficient than a bubble sort on large lists.
But it uses more memory, because the sublists must be stored separately during the process. Bubble sort works in place and needs almost no extra memory.
Key points
- A merge sort splits then merges.
- It uses divide and conquer.
- Splitting continues until sublists have one item.
- A one-item list is already sorted.
- Merging compares the first item of each sublist.
- It is faster than bubble sort but uses more memory.
Worked examples
Example 1
Merge the sorted sublists 2, 7 and 3, 5. [3 marks]
Working
Example 2
Explain why splitting stops when sublists contain one item. [2 marks]
Working
Example 3
State one advantage and one disadvantage of merge sort compared with bubble sort. [2 marks]
Working
Common mistakes
Merging without comparing.
Each merge compares the first items of the two sublists.
Stopping the split too early.
Split until every sublist has exactly one item.
Forgetting to append the remaining items.
When one sublist empties, the rest of the other is appended.
Saying merge sort uses less memory.
It uses more, because sublists are stored separately.
Exam tips
- Show the splitting and merging phases separately.
- Compare only the first item of each sublist.
- Remember to append leftovers when one sublist empties.
- Contrast efficiency and memory with bubble sort.
Key terms
- Merge sort
- Sorting by splitting into single items then merging.
- Divide and conquer
- Splitting a problem into parts, solving each, then combining.
- Sublist
- A smaller list produced by splitting.
- Merge
- Combining two sorted lists into one sorted list.
Related topics
Written and reviewed against the current AQA specification. Spotted an error? Let us know.