A sorting algorithm is a precise method for rearranging items in a list into a defined order — usually ascending or descending. For GCSE Computer Science, you need to understand and trace bubble sort and merge sort, compare their efficiency, and explain why choosing the right algorithm matters.
Why do we need sorting algorithms?
Computers sort data constantly: a music app orders songs alphabetically, a school database ranks students by mark, a search engine orders results by relevance. Sorting is also a building block for other algorithms — binary search, for example, only works on a sorted list. The AQA and OCR GCSE specifications both require students to trace, write, and evaluate sorting algorithms, so this topic appears reliably in exams.
How does bubble sort work?
Bubble sort repeatedly passes through the list, comparing adjacent pairs of items and swapping them if they are in the wrong order. Larger values "bubble up" towards the end of the list with each pass.
Worked example — sort [5, 3, 8, 1, 4] into ascending order:
Pass 1:
| Comparison | List state | Swap? |
|---|---|---|
| 5 vs 3 | [3, 5, 8, 1, 4] | Yes |
| 5 vs 8 | [3, 5, 8, 1, 4] | No |
| 8 vs 1 | [3, 5, 1, 8, 4] | Yes |
| 8 vs 4 | [3, 5, 1, 4, 8] | Yes |
After Pass 1: [3, 5, 1, 4, 8] — 8 is now in its correct position.
Pass 2:
| Comparison | List state | Swap? |
|---|---|---|
| 3 vs 5 | [3, 5, 1, 4, 8] | No |
| 5 vs 1 | [3, 1, 5, 4, 8] | Yes |
| 5 vs 4 | [3, 1, 4, 5, 8] | Yes |
After Pass 2: [3, 1, 4, 5, 8] — 5 and 8 are in position.
Subsequent passes continue until no swaps occur in a full pass, meaning the list is sorted.
The key insight: after each pass, at least one more element is guaranteed to be in its final position. An optimisation is to stop early if a complete pass produces zero swaps.
How does merge sort work?
Merge sort uses a divide and conquer strategy:
- Divide the list in half repeatedly until each sub-list contains only one element (a single element is by definition sorted).
- Merge pairs of sub-lists back together in sorted order.
Worked example — sort [5, 3, 8, 1]:
Divide phase:
- [5, 3, 8, 1] → [5, 3] and [8, 1]
- [5, 3] → [5] and [3]
- [8, 1] → [8] and [1]
Merge phase:
- Merge [5] and [3] → [3, 5] (3 < 5, so 3 goes first)
- Merge [8] and [1] → [1, 8]
- Merge [3, 5] and [1, 8] → compare 3 vs 1 → take 1; compare 3 vs 8 → take 3; compare 5 vs 8 → take 5; take 8 → [1, 3, 5, 8]
Each merge step works by repeatedly taking the smaller of the two front elements from the sub-lists being merged.
Bubble sort vs merge sort: a comparison
| Feature | Bubble sort | Merge sort |
|---|---|---|
| Strategy | Compare and swap adjacent pairs | Divide, then merge |
| Best-case comparisons | O(n) — already sorted, one pass | O(n log n) — always divides |
| Worst-case comparisons | O(n²) | O(n log n) |
| Memory use | In-place (no extra list needed) | Needs extra memory for merging |
| Suitable for | Small lists, simple implementation | Large lists where speed matters |
| Exam boards | AQA, OCR, Edexcel | AQA, OCR, Edexcel |
What is O(n²) and O(n log n)? These are Big O notations expressing how the number of steps grows as the list size n increases. For n = 1,000: bubble sort may need up to 1,000,000 comparisons; merge sort needs roughly 10,000. This difference becomes enormous for large datasets.
What is the difference between stable and unstable sorting?
A sorting algorithm is stable if it preserves the original relative order of items with equal keys. Merge sort is stable; basic bubble sort is also stable. Stability matters when sorting a table by one column that already has records sorted by another — for example, sorting a list of students by grade while preserving alphabetical order within each grade group.
How do you trace a sorting algorithm in an exam?
Examiners typically ask you to show each pass or merge step. Follow these rules:
- Show every comparison, not just the swaps.
- Underline or highlight the pair being compared.
- Write the full list state after every swap (not just at the end of a pass).
- State explicitly when the algorithm terminates and why.
Losing marks on trace questions is almost always due to skipping intermediate states. Treat it like showing working in mathematics.
When would a programmer choose bubble sort over merge sort?
Bubble sort is taught primarily because it is easy to understand and implement. In professional software, it is rarely chosen over merge sort for large lists. However, bubble sort can be the better choice when:
- The list is nearly sorted (the optimised version terminates in O(n) time).
- The list is very short (the overhead of merge sort's recursion is not worth it).
- Memory is severely constrained (bubble sort is in-place; merge sort needs extra space).
Frequently asked questions
How many passes does bubble sort need in the worst case?
In the worst case (a completely reversed list of n items), bubble sort needs n − 1 passes. Each pass places at least one element in its correct final position, but the algorithm has no way to skip earlier positions. With the optimisation of stopping when no swaps occur, the algorithm may terminate sooner — but in the worst case it still needs n − 1 passes.
Do I need to know merge sort's pseudocode for GCSE?
For AQA and OCR GCSE Computer Science, you are expected to trace merge sort through given examples and understand how it works. Writing full pseudocode from memory is less commonly examined than tracing, but being able to describe the divide-and-conquer steps in words or pseudocode is excellent exam preparation. Check your specific specification for the exact requirement.
What is Big O notation and do I need it for GCSE?
Big O notation describes how the running time of an algorithm scales with the size of the input. GCSE specifications mention efficiency and comparing algorithms, and terms like O(n²) and O(n log n) may appear in mark schemes or specification glossaries. You do not need to derive Big O mathematically at GCSE — you need to understand that O(n²) grows much faster than O(n log n) and can explain why merge sort is more efficient for large lists.
Why does merge sort always take O(n log n) even in the best case?
Merge sort always divides the list fully, regardless of its initial order. It cannot detect that the list is already sorted and skip work the way optimised bubble sort can. This means its best case equals its worst case: O(n log n). The guaranteed upper bound is actually a strength — unlike bubble sort, its performance never degrades catastrophically on a large reversed list.
For Socratic GCSE Computer Science tutoring — sorting algorithms, data structures, and beyond — visit aitutors.me.