What bubble sort does
Bubble sort repeatedly compares adjacent numbers and swaps them if the left one is larger.
- Start at the left and compare each adjacent pair, swapping when out of order.
- After one pass the largest remaining number has been carried to the right end, and that position is fixed.
- The next pass only needs to cover the part that is not yet fixed.
- If a pass makes no swaps at all, the array is sorted and we can stop early.
Why it is O(n²)
n numbers need at most n − 1 passes of at most n − 1 comparisons each: n(n − 1) / 2 comparisons in total. On a reversed array every comparison swaps, so swaps are also n(n − 1) / 2 — the numbers shown by the “Worst case” button above.
On sorted data the first pass makes no swaps and ends after n − 1 comparisons.
Complexity
| Best | O(n) |
|---|---|
| Average | O(n²) |
| Worst | O(n²) |
| Extra space | O(1) |
| Stable | Yes |
FAQ
- Why is it called bubble sort?
- Each pass carries the current largest value all the way to the right, like a bubble rising to the surface.
- Is the best case really O(n)?
- Only with the optimisation that stops when a pass makes no swaps. Without it the algorithm is O(n²) on any input. The animation here includes that optimisation.
- Is bubble sort stable?
- Yes. It swaps only when the left value is strictly greater than the right one, so equal values never trade places.