What is Bubble Sort?
Bubble sort is a sorting algorithm that repeatedly steps through the list, compares adjacent pairs of elements, and swaps them if they are in the wrong order. After each full pass through the list, the largest unsorted element "bubbles up" to its correct position at the end.
The Edexcel 4CP0 specification requires you to understand, trace, and write pseudocode for bubble sort. Note: insertion sort is NOT in the Edexcel spec — only bubble sort and merge sort.
How Bubble Sort Works — Step by Step
- Start at the beginning of the list
- Compare element at position i with element at position i+1
- If element[i] > element[i+1] → swap them
- Move to the next pair (i+1 and i+2)
- Continue to the end of the unsorted portion of the list
- After each pass, the last unsorted element is in its correct position
- Repeat until no swaps are made in a pass (list is sorted)
Worked Example
Sort: [5, 3, 8, 1, 9, 2]
| Pass | List after pass | Swaps? |
|---|
| Pass 1 | [3, 5, 1, 8, 2, 9] | Yes |
| Pass 2 | [3, 1, 5, 2, 8, 9] | Yes |
| Pass 3 | [1, 3, 2, 5, 8, 9] | Yes |
| Pass 4 | [1, 2, 3, 5, 8, 9] | Yes |
| Pass 5 | [1, 2, 3, 5, 8, 9] | No → STOP |
Efficiency
- Best case: O(n) — already sorted, one pass with no swaps
- Worst case: O(n²) — reverse sorted, maximum comparisons and swaps
- Bubble sort is simple but inefficient for large datasets
📝 Exam Tip: When tracing bubble sort, show the state of the entire list after each complete pass (not after each individual swap). Count the number of passes and swaps — both may be asked.
⚠️ Common Mistakes
- Stopping after a fixed number of passes instead of continuing until no swaps occur
- Forgetting to reduce the comparison range after each pass (last element of each pass is already sorted)
- Confusing bubble sort with merge sort — they work completely differently