Bubble sort
Bubble sort repeatedly scans the unsorted portion of the array, comparing each pair of adjacent values and swapping them if they are in the wrong order. Each full pass moves the largest remaining value into its correct position at the end of the array, so the array is sorted after at most n − 1 passes.
When it is the right choice
Bubble sort is genuinely not worth using in practice: insertion sort does the same job or better on every input while making far fewer writes, and any general-purpose language ships a library sort that outperforms both by a wide margin. Its only real value is pedagogical, as the simplest sorting algorithm to trace by hand. The early-exit optimisation below gives it a best case of O(n) on already-sorted input, but that is not a reason to reach for it.
How it works
- Walk the array from the first index to the last unsorted index, comparing each value with its neighbour to the right.
- Swap the pair if the left value is greater than the right value.
- After each pass, the largest remaining value has moved into place, so the unsorted portion shrinks by one from the right.
- Track whether any swap happened during a pass; if none did, the array is already sorted and the algorithm stops early.
Worth noticing
- It performs up to O(n²) swaps as well as O(n²) comparisons, which is worse than selection sort's O(n) swaps — this is why it is slower in practice despite sharing the same worst-case complexity.
- The early-exit check only helps on nearly-sorted input; on reversed input it still runs the full O(n²) passes.
- It is stable — equal elements keep their relative order — which matters less than it might seem for a sort this slow.
Cost
- Best
- O(n)
- Average
- O(n²)
- Worst
- O(n²)
- Extra space
- O(1)
- Stable
- Yes