CS4: Sorting Algorithms
How bubble sort and merge sort work, with step-by-step examples, comparisons, and time complexity analysis.
📋 What is a Sorting Algorithm?
Definition: A sorting algorithm arranges the elements of a list into a particular order (usually ascending or descending). Sorting makes data easier to search, read, and process.
At GCSE, you need to know two sorting algorithms:
- Bubble sort - repeatedly swaps adjacent elements that are in the wrong order
- Merge sort - divides the list, sorts sublists, then merges them back together
🔵 Bubble Sort
Bubble sort works by repeatedly stepping through the list, comparing each pair of adjacent items, and swapping them if they are in the wrong order. After each pass, the largest unsorted element "bubbles up" to its correct position at the end of the list.
Algorithm in Pseudo-code
Bubble Sort Pseudo-code
PROCEDURE bubbleSort(list)
n ← LENGTH(list)
swapped ← TRUE
WHILE swapped
swapped ← FALSE
FOR i ← 0 TO n - 2
IF list[i] > list[i + 1] THEN
temp ← list[i]
list[i] ← list[i + 1]
list[i + 1] ← temp
swapped ← TRUE
ENDIF
NEXT i
n ← n - 1
ENDWHILE
ENDPROCEDURE
Step-by-Step Worked Example
Sorting [5, 3, 8, 1, 2] using bubble sort
Pass 1:
| Comparison | Pair | Action | List State |
|---|---|---|---|
| 1 | 5, 3 | 5 > 3 → Swap | [3, 5, 8, 1, 2] |
| 2 | 5, 8 | 5 < 8 → No swap | [3, 5, 8, 1, 2] |
| 3 | 8, 1 | 8 > 1 → Swap | [3, 5, 1, 8, 2] |
| 4 | 8, 2 | 8 > 2 → Swap | [3, 5, 1, 2, 8] |
8 is now in its correct position. Swapped = TRUE.
Pass 2:
| Comparison | Pair | Action | List State |
|---|---|---|---|
| 1 | 3, 5 | 3 < 5 → No swap | [3, 5, 1, 2, 8] |
| 2 | 5, 1 | 5 > 1 → Swap | [3, 1, 5, 2, 8] |
| 3 | 5, 2 | 5 > 2 → Swap | [3, 1, 2, 5, 8] |
5 is now in its correct position. Swapped = TRUE.
Pass 3:
| Comparison | Pair | Action | List State |
|---|---|---|---|
| 1 | 3, 1 | 3 > 1 → Swap | [1, 3, 2, 5, 8] |
| 2 | 3, 2 | 3 > 2 → Swap | [1, 2, 3, 5, 8] |
Swapped = TRUE.
Pass 4:
| Comparison | Pair | Action | List State |
|---|---|---|---|
| 1 | 1, 2 | 1 < 2 → No swap | [1, 2, 3, 5, 8] |
Swapped = FALSE → Sort complete!
Final result: [1, 2, 3, 5, 8]
Bubble Sort Performance:
Worst case comparisons: n(n-1)/2 ≈ O(n²)
Best case (already sorted): O(n) - one pass with no swaps
Average case: O(n²)
Memory: O(1) - sorts in place, no extra memory needed
Worst case comparisons: n(n-1)/2 ≈ O(n²)
Best case (already sorted): O(n) - one pass with no swaps
Average case: O(n²)
Memory: O(1) - sorts in place, no extra memory needed
🟢 Merge Sort
Merge sort uses a "divide and conquer" approach. It splits the list into individual elements, then repeatedly merges pairs of sorted sublists until the whole list is recombined in order.
Algorithm in Pseudo-code
Merge Sort Pseudo-code
PROCEDURE mergeSort(list)
IF LENGTH(list) <= 1 THEN
RETURN list
ENDIF
mid ← LENGTH(list) DIV 2
leftHalf ← mergeSort(list[0:mid])
rightHalf ← mergeSort(list[mid:LENGTH(list)])
RETURN merge(leftHalf, rightHalf)
ENDPROCEDURE
PROCEDURE merge(left, right)
result ← []
WHILE LENGTH(left) > 0 AND LENGTH(right) > 0
IF left[0] <= right[0] THEN
APPEND left[0] TO result
REMOVE left[0] FROM left
ELSE
APPEND right[0] TO result
REMOVE right[0] FROM right
ENDIF
ENDWHILE
APPEND remaining items FROM left TO result
APPEND remaining items FROM right TO result
RETURN result
ENDPROCEDURE
Step-by-Step Worked Example
Sorting [5, 3, 8, 1] using merge sort
Phase 1: Divide
[5, 3, 8, 1]
/ \
[5, 3] [8, 1]
/ \ / \
[5] [3] [8] [1]
Phase 2: Merge
Merge [5] and [3] → 3 < 5 → [3, 5] Merge [8] and [1] → 1 < 8 → [1, 8] Merge [3, 5] and [1, 8]: Compare 3 and 1 → 1 → [1] Compare 3 and 8 → 3 → [1, 3] Compare 5 and 8 → 5 → [1, 3, 5] Remaining: [8] → [1, 3, 5, 8]
Final result: [1, 3, 5, 8]
Merge Sort Performance:
All cases: O(n log n)
The divide step creates log n levels
Each level requires n comparisons during merging
Memory: O(n) - needs extra space for temporary arrays
All cases: O(n log n)
The divide step creates log n levels
Each level requires n comparisons during merging
Memory: O(n) - needs extra space for temporary arrays
⚖️ Comparing Bubble Sort and Merge Sort
| Feature | Bubble Sort | Merge Sort |
|---|---|---|
| Approach | Repeatedly swap adjacent items | Divide and conquer, then merge |
| Best case | O(n) | O(n log n) |
| Average case | O(n²) | O(n log n) |
| Worst case | O(n²) | O(n log n) |
| Memory usage | O(1) - in place | O(n) - needs extra space |
| Implementation | Simple to understand and code | More complex, uses recursion |
| Stable sort | Yes | Yes |
| Good for small lists | Yes - simple and adequate | Overkill - overhead of recursion |
| Good for large lists | No - very slow | Yes - much more efficient |
📊 Efficiency Comparison with Numbers
How many comparisons for different list sizes?
| List Size (n) | Bubble Sort (n²) | Merge Sort (n log n) | Ratio |
|---|---|---|---|
| 10 | 100 | 33 | 3x |
| 100 | 10,000 | 664 | 15x |
| 1,000 | 1,000,000 | 9,966 | 100x |
| 10,000 | 100,000,000 | 132,877 | 753x |
As the list grows, merge sort becomes dramatically faster than bubble sort.
⚠️ Common Mistakes
| Mistake | Why It's Wrong | How to Fix It |
|---|---|---|
| Stopping bubble sort after n-1 passes always | You can stop early if no swaps occurred in a pass | Use a 'swapped' flag to detect when sorted |
| Forgetting to reduce n in bubble sort | The last elements are already sorted after each pass | After each pass, the next pass has one fewer comparison |
| Not handling the "remaining items" in merge | One sublist may still have items left | Append all remaining items from both sublists |
| Saying merge sort is always better | Bubble sort uses less memory and is simpler for small lists | Consider the context: list size, memory constraints |
❓ Practice Questions
Q1: Show the state of the list [4, 2, 7, 1] after each pass of bubble sort.
Q2: Describe the two phases of merge sort.
Q3: Why is merge sort more efficient than bubble sort for large datasets?
Q4: Give one advantage of bubble sort over merge sort.
Q5: How many comparisons would bubble sort make in the worst case for a list of 50 items?
✅ Answers
- Pass 1: Compare 4,2 → swap → [2,4,7,1]. Compare 4,7 → no swap. Compare 7,1 → swap → [2,4,1,7]. Pass 2: Compare 2,4 → no swap. Compare 4,1 → swap → [2,1,4,7]. Pass 3: Compare 2,1 → swap → [1,2,4,7]. Pass 4: No swaps → sorted.
- Phase 1 (Divide): Split the list recursively into smaller sublists until each sublist contains one element. Phase 2 (Merge): Repeatedly merge pairs of sorted sublists by comparing the first elements and building new sorted lists.
- Merge sort has O(n log n) time complexity while bubble sort has O(n²). As n grows large, n² grows much faster than n log n, so bubble sort becomes extremely slow while merge sort remains relatively efficient.
- Bubble sort uses O(1) memory (sorts in place) while merge sort needs O(n) extra memory. Bubble sort is also simpler to implement and understand.
- Worst case: n(n-1)/2 = 50 × 49 / 2 = 1225 comparisons.
🎯 Exam Tips
- Practise showing bubble sort step-by-step with a table showing each comparison and swap
- For merge sort, draw the divide tree and show each merge step
- Remember: bubble sort can stop early if a pass has no swaps
- When comparing, always mention time complexity: O(n²) vs O(n log n)
- Don't forget memory: bubble sort is in-place, merge sort needs extra space
- In the exam, show ALL your working - you get marks for each step, not just the final answer
⚠️ Common Errors
✗ Thinking bubble sort is the most efficient sorting algorithm ✓ Bubble sort has O(n²) time complexity, making it inefficient for large datasets. Merge sort (O(n log n)) is more efficient for large amounts of data.
✗ Confusing the pass logic in bubble sort — thinking one pass fully sorts the list ✓ One pass of bubble sort moves the largest unsorted element to its correct position; it takes n-1 passes to fully sort a list of n elements.
✗ Believing merge sort requires no extra memory ✓ Merge sort requires additional memory to merge sub-lists (O(n) space complexity), unlike bubble sort which sorts in-place.
✗ Thinking insertion sort is always O(n²) ✓ Insertion sort is O(n²) in the worst and average cases, but O(n) in the best case when the data is already nearly sorted.
✍️ Model Answer
Full-Mark Response
A school stores 2000 student records that need to be sorted by surname. Compare bubble sort and merge sort for this task, explaining which is more suitable and why. [5 marks]
Bubble sort has O(n²) time complexity. For 2000 records, this means up to approximately 4,000,000 comparisons in the worst case. It sorts in-place, so uses minimal extra memory. Merge sort has O(n log n) time complexity. For 2000 records, this means approximately 2000 × 11 = 22,000 comparisons, which is far fewer. However, it requires O(n) extra memory for merging. Merge sort is more suitable because 2000 records is a large dataset where the difference between O(n²) and O(n log n) is significant. The faster sorting time outweighs the extra memory cost on modern systems. Bubble sort would be impractically slow for this volume of data.
📊 AO Deep Dive
Assessment Objective Analysis
AO1 (Computational Thinking — 40%): Demonstrate knowledge and understanding of the principles and concepts of computer science, including sorting algorithms: bubble sort and merge sort for AQA 8525, OCR J277 & Edexcel 1CP2.
AO2 (Application — 40%): Apply knowledge and understanding of computer science, including sorting algorithms: bubble sort and merge sort to analyse problems in computational terms and to design, write and evaluate solutions.
AO3 (Evaluation — 20%): Evaluate the effectiveness, correctness and efficiency of computational solutions, including sorting algorithms: bubble sort and merge sort, and make reasoned judgements about trade-offs.
📝 Exam Technique
GCSE Computer Science Exam Tips:
When comparing sorting algorithms, always give the time complexity of each and explain what it means for the given dataset size. Mention trade-offs: bubble sort is simple and in-place but slow; merge sort is fast but uses extra memory. For bubble sort questions, describe how each pass works and that n-1 passes are needed. Show the comparison count for a specific n to illustrate efficiency differences.
When comparing sorting algorithms, always give the time complexity of each and explain what it means for the given dataset size. Mention trade-offs: bubble sort is simple and in-place but slow; merge sort is fast but uses extra memory. For bubble sort questions, describe how each pass works and that n-1 passes are needed. Show the comparison count for a specific n to illustrate efficiency differences.
📝 Exam Questions by Topic
🎬 Video Resources
Ready to ace your GCSE Computer Science exams?
Get the best revision books and guides to boost your grades.