Overview
Bubble Sort is the classic introductory sorting algorithm. It repeatedly steps through the list, compares each pair of adjacent elements, and swaps them if they are in the wrong order, so the largest values gradually 'bubble' to the end.
Because it only ever compares neighbours, Bubble Sort is trivial to reason about and to implement, which is why it is taught first — even though it is far too slow for large inputs.
How Bubble Sort works
- Compare the first two adjacent elements; swap them if the left one is larger.
- Move one position to the right and repeat to the end of the array — after this pass the largest element sits last.
- Repeat the passes over the still-unsorted prefix, which shrinks by one each time.
- Stop early if a full pass makes no swaps — the array is already sorted.
When to use it
- Teaching the idea of comparison-and-swap sorting to beginners.
- Tiny or nearly-sorted arrays, where its early-exit makes it effectively linear.
- Avoid it on large datasets — quadratic time makes it impractical.
Complexity analysis
Each of the n passes may scan up to n elements, giving O(n²) comparisons in the average and worst cases. A best case of O(n) occurs on already-sorted input thanks to the no-swap early exit. It sorts in place (O(1) extra space) and is stable.
Frequently asked questions
Is Bubble Sort stable?
Yes. It only swaps strictly out-of-order neighbours, so equal elements keep their original relative order.
Why is Bubble Sort considered inefficient?
It performs O(n²) comparisons and many redundant swaps, so faster O(n log n) sorts like Merge Sort or Quick Sort are preferred for real workloads.