Bubble sort is one of the simplest sorting algorithms in computer science — it repeatedly steps through a list, compares neighbouring pairs of elements, and swaps them if they are in the wrong order. This process repeats until an entire pass finds nothing to swap, confirming the list is sorted.
What is the core idea behind bubble sort?
The name comes from the way larger values gradually "bubble" towards the end of the list with each pass. Think of a line of students arranged by height: you walk along the line, and wherever two adjacent students are in the wrong order you swap them. After one walk, the tallest student is guaranteed to be at the end. Repeat the walk for the remaining students and the second-tallest drifts to the correct position, and so on.
Importantly, you can stop early if you complete a full pass without making a single swap — that proves every pair is already in order and the list is sorted.
How does one pass of bubble sort work? A step-by-step example
Starting list: [5, 3, 8, 1, 4] — sort ascending.
Pass 1:
| Step | Comparison | Swap? | List after step |
|---|---|---|---|
| 1 | 5 vs 3 | Yes (5 > 3) | [3, 5, 8, 1, 4] |
| 2 | 5 vs 8 | No | [3, 5, 8, 1, 4] |
| 3 | 8 vs 1 | Yes (8 > 1) | [3, 5, 1, 8, 4] |
| 4 | 8 vs 4 | Yes (8 > 4) | [3, 5, 1, 4, 8] |
After Pass 1, the value 8 has correctly bubbled to position 4 (the last index). The algorithm now needs only 4 comparisons on Pass 2, then 3, then 2, and so on.
How is bubble sort written in pseudocode?
PROCEDURE bubbleSort(list)
n ← LENGTH(list)
FOR i ← 0 TO n - 2
swapped ← FALSE
FOR j ← 0 TO n - 2 - i
IF list[j] > list[j + 1] THEN
temp ← list[j]
list[j] ← list[j + 1]
list[j + 1] ← temp
swapped ← TRUE
END IF
END FOR
IF swapped = FALSE THEN
RETURN // early exit: list is already sorted
END IF
END FOR
END PROCEDURE
The swapped flag implements the early-exit optimisation. Without it the algorithm always performs the full O(n²) passes even on a list that was nearly sorted from the start.
What is bubble sort's time complexity?
| Case | Comparisons | Big O | When it occurs |
|---|---|---|---|
| Best case | n − 1 | O(n) | List is already sorted (with early-exit flag) |
| Average case | n(n−1) / 4 | O(n²) | Random order |
| Worst case | n(n−1) / 2 | O(n²) | List is sorted in reverse |
The worst-case O(n²) means that doubling the list roughly quadruples the work. For a list of 1,000 items, that is roughly 500,000 comparisons. Compare this with merge sort's O(n log n), which handles 1,000 items in around 10,000 operations. Bubble sort is therefore impractical for large datasets.
How does bubble sort compare with other sorting algorithms?
| Algorithm | Worst-case time | Space | Stable? | Easy to implement? |
|---|---|---|---|---|
| Bubble sort | O(n²) | O(1) | Yes | Very easy |
| Insertion sort | O(n²) | O(1) | Yes | Easy |
| Selection sort | O(n²) | O(1) | No | Easy |
| Merge sort | O(n log n) | O(n) | Yes | Moderate |
| Quicksort | O(n²) worst / O(n log n) avg | O(log n) | No | Moderate |
A stable sort preserves the relative order of equal elements. Bubble sort is stable because it only swaps when an element is strictly greater than its neighbour, so equal elements never overtake each other.
When is bubble sort actually used?
Honestly, bubble sort is almost never the right choice in professional software. Its strength lies in pedagogy: the algorithm is easy to visualise, easy to trace, and easy to code, making it ideal for learning how sorting works. The only genuine practical scenario is a nearly sorted list where the early-exit optimisation makes the best-case O(n) highly likely. Even then, insertion sort handles the same case at least as well.
At GCSE, you are expected to know how bubble sort works, be able to trace through it, and compare its efficiency with other algorithms. You are not expected to advocate for it in real systems.
Frequently asked questions
Do I need to memorise the pseudocode for bubble sort in the GCSE exam?
You should understand the logic well enough to write or complete pseudocode, but most GCSE mark schemes reward correct description of the comparisons, swaps, and passes rather than exact syntax. Focus on understanding the process: compare adjacent pairs, swap if out of order, repeat passes, use an early-exit flag for efficiency.
Why is bubble sort described as O(n²) when the best case is O(n)?
Big O notation conventionally describes the worst-case growth rate. Bubble sort performs O(n²) comparisons in the worst and average cases, which is the situation examiners test against. The O(n) best case only applies with the early-exit flag and a pre-sorted list — a special case, not the typical scenario.
What does "stable sort" mean and why does it matter?
A stable sorting algorithm preserves the original relative order of elements that are considered equal. If two students have the same mark, a stable sort keeps them in the same order as the original list. Bubble sort is stable. This matters in real applications — for instance, first sort by surname, then stably sort by class, and the surname order within each class is preserved.
How many passes does bubble sort need to sort a list of n items?
In the worst case (reverse-sorted list), bubble sort needs n − 1 passes. After each pass, at least one more element reaches its final position at the end of the unsorted portion. With the early-exit optimisation, the algorithm may terminate after fewer passes if the list becomes sorted before all n − 1 passes are complete.
Want to trace bubble sort with your own lists and get instant feedback? Professor Turing at aitutors.me will walk you through every swap.