Algorithms and programming · GCSE Computer Science
Merge sort
GCSE Computer Science merge sort: split the list to one-item pieces, merge sorted halves back together, and compare time and extra memory with bubble sort.
Split until every list has one item (those are sorted). Merge pairs by always taking the smaller head. Faster on large n than bubble; needs extra space.
The important bits
What you need to know
- 1
Merge sort is divide-and-conquer: split the list into two halves, sort each half (by merging again), then merge the two sorted halves into one sorted list.
- 2
A list of length 1 is already sorted. The splitting phase continues until every piece is a single item; the work that actually orders data is the merge.
- 3
Merging two sorted lists: compare the front item of each, copy the smaller into the output, and advance that list. When one list is empty, copy the rest of the other.
- 4
The merge needs extra memory — an output array (or new lists) the size of the combined halves. Bubble sort is in-place; merge sort is not. That is the space comparison.
- 5
Time is consistently better than bubble on large n: you do not do n² neighbour swaps. Each item is copied through a logarithmic number of merge levels. GCSE may say “more efficient for large lists”.
- 6
Unlike bubble’s flag, merge sort does not get a special bargain on already-sorted data in the basic version — it still splits and merges. It also does not get much worse on reverse-sorted data.
- 7
Trace questions often give a small list and want the split tree plus each merge. Write the sublists explicitly: [6, 3, 8, 2] → [6, 3] and [8, 2], and so on.
- 8
You cannot skip the extra array in a written answer if they ask about memory. “Merge is better” without time versus space is a 2-mark gift thrown away.
Quotations worth analysing
Short evidence. Real method.
“Split the list into two halves and merge the sorted halves back together.”
Both verbs score: split and merge. Writing only “it divides the list” without describing the merge loses the algorithm.
“A list of one item is already sorted.”
This is why splitting stops. The sort happens when sorted runs are merged, not when the list is first cut in half.
“Merge sort uses additional memory; bubble sort sorts in place.”
Time and space are different marks. Merge is usually faster on large n; bubble needs only a handful of extra variables.
Go deeper
The merge is the algorithm; the split is the setup
Students draw a pretty binary tree of splits and then forget to merge. Marks live on the way back up. Two sorted lists [3, 6] and [2, 8] merge as: 2 is smaller than 3, take 2; 3 is smaller than 8, take 3; 6 is smaller than 8, take 6; copy 8. Output [2, 3, 6, 8]. You always compare the current heads, never scan at random. If one half runs out, the remainder of the other half is already sorted, so you append it. That rule is the whole merge. In a trace, write both input halves and the growing output. If the paper uses 0-based indexes to mark the split point, mid = n DIV 2, left gets the first mid items, right gets the rest — an odd-length list is allowed and one half is simply longer by one.
Go deeper
Time versus space versus bubble, without mythology
Bubble sort is visible: adjacent compares, swap, flag, repeat. On reverse-sorted data it does a lot of pointless work; on nearly-sorted data a flag can exit early; extra memory is tiny. Merge sort splits to length one then merges by always taking the smaller head. It is consistently faster on large n because the number of levels is small compared with n, and each level copies the items a linear number of times. The bill is extra space for the merged copy and more complex code to hand-trace. If a 6-mark question asks you to compare, use time, space, and whether the data is likely already sorted — not “merge is better because it is more advanced”. For four items, they still want the split/merge diagram. Do not skip it to write an essay about Big O unless the specification named Big O.
See the idea in action
Merge sort [6, 3, 8, 2]. Split: [6, 3, 8, 2] → [6, 3] and [8, 2]. Split: [6, 3] → [6] and [3]. Split: [8, 2] → [8] and [2]. Merge [6] and [3]: 3 < 6 so [3, 6]. Merge [8] and [2]: 2 < 8 so [2, 8]. Merge [3, 6] and [2, 8]: Heads 3 and 2 → take 2. Output [2]. Heads 3 and 8 → take 3. Output [2, 3]. Heads 6 and 8 → take 6. Output [2, 3, 6]. Right half left [8] → append. Sorted list [2, 3, 6, 8]. Bubble sort on the same list would swap neighbours through several passes and need no extra array. Merge used extra lists at each merge; it did not need a nearly-sorted flag.
Exam technique
Turn knowledge into marks
Draw the split all the way to single items, then merge by always taking the smaller head. In a compare question, mention time on large n and the extra memory versus bubble sort’s in-place swaps.
Common mistakes
Do not give these marks away
- 01
Describing only the splitting stage and never explaining how two sorted halves are merged.
- 02
Saying merge sort is better in every way, forgetting that it needs additional memory and is harder to dry-run by hand.
- 03
Merging by concatenating the two halves without comparing heads, which does not sort.
Compared with bubble sort, merge sort typically
AUses no extra memory and is slower on large lists
BNeeds extra memory for merging and is more time-efficient on large lists
COnly works if the list is already sorted
DCompares only neighbouring items and swaps them in place
Show the answer
Needs extra memory for merging and is more time-efficient on large lists. The merge copies items into an additional structure, so space is higher than in-place bubble sort. Time is better on large n. Merge sort does not require a pre-sorted list; that is binary search.
Quick questions
If this is the bit you searched
How does merge sort work GCSE?
The list is split into halves until each piece has one item. Sorted pieces are then merged by repeatedly taking the smaller front item of the two halves until one sorted list remains.
Why does merge sort need extra space?
The merge builds a new combined list (or array) while the two halves still exist. Bubble sort only swaps inside the original list, so it is in-place.
Is merge sort faster than bubble sort?
On large lists, usually yes, because you are not doing a quadratic pile of neighbour swaps. On a tiny list the difference is small, and bubble may finish early if a flag detects it is already sorted.
Does merge sort require the list to be sorted first?
No. Sorting is the job it performs. Binary search is the algorithm that requires a sorted list before you start.