Cambridge IGCSE Computer Science (0478) · lesson 28 of 35 · 25 min
Bubble Sort
Bubble sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. After each pass, the largest unsorted element “bubbles” to its correct position at the end.
Worst case: O(n²) comparisons. Best case (already sorted): O(n) with optimisation.
Bubble sort pass 1 on [5, 3, 8, 1, 4]
After pass 1, 8 is in its correct position. Repeat for remaining elements.
Merge Sort
Merge sort uses a divide-and-conquer approach:
- Divide: Split the list in half repeatedly until each sublist has one element.
- Conquer: Single-element lists are trivially sorted.
- Merge: Merge pairs of sorted sublists by comparing their front elements and taking the smaller one each time.
Time complexity: O(n log n) always — much better than bubble sort for large lists.
Merge sort on [5, 3, 8, 1]
Split: [5, 3] | [8, 1]
Split: [5] [3] | [8] [1]
Merge [5][3] → [3, 5]
Merge [8][1] → [1, 8]
Merge [3,5][1,8] → [1, 3, 5, 8] ✓
Comparison
After one complete pass of bubble sort on [4, 2, 7, 1], which element is guaranteed to be in its final position?
- 4
- 1
- 7
- 2
Answer: 2
The largest element (7) bubbles to the end after one pass.
What is the time complexity of merge sort?
- O(n)
- O(n²)
- O(n log n)
- O(log n)
Answer: O(n log n)
Merge sort is O(n log n) in all cases.
Merge sort uses which algorithmic strategy?
- Greedy
- Dynamic programming
- Divide and conquer
- Backtracking
Answer: Divide and conquer
Merge sort divides the list, sorts each half, then merges — classic divide and conquer.
Previous lesson: Linear search and binary search
Back to Cambridge IGCSE Computer Science (0478)
Next lesson: Variables, constants, and data types