Bubble sort is a simple comparison-based sorting algorithm that repeatedly walks through a list, compares each pair of adjacent elements and swaps them when they are in the wrong order. After each full pass, the largest remaining element has moved, or bubbled, to its final position at the end, and the process repeats until a pass makes no swaps.
Among algorithms taught in programming courses, bubble sort is a classic first example because its logic is easy to follow and to prove correct. Its quadratic time complexity makes it impractical for large inputs, so in production code it is almost always replaced by quicksort, merge sort or a library sort.
How bubble sort moves elements into place
Bubble sort works in passes. In each pass it compares positions 0 and 1, then 1 and 2, and so on up to the last unsorted position, swapping any pair where the left value is larger than the right one. Because the largest value is carried along by every swap it takes part in, it reaches the end of the unsorted region in a single pass.
After pass k, the last k elements are in their final positions, so each subsequent pass can stop one position earlier. A list of n elements therefore needs at most n − 1 passes. The common early-exit optimization tracks whether any swap happened during a pass; if none did, the list is already sorted and the algorithm stops.
The table below traces the first pass over a short list.
| Step | Compared pair | Action | List after step |
|---|---|---|---|
| 1 | 5 and 1 | Swap | 1, 5, 4, 2, 8 |
| 2 | 5 and 4 | Swap | 1, 4, 5, 2, 8 |
| 3 | 5 and 2 | Swap | 1, 4, 2, 5, 8 |
| 4 | 5 and 8 | No swap | 1, 4, 2, 5, 8 |
After this pass, 8 is fixed at the end. The second pass swaps 4 and 2, and a third pass finds no swaps, so the early-exit check ends the sort with the list 1, 2, 4, 5, 8.
Time and space complexity of bubble sort
Bubble sort performs up to n(n − 1)/2 comparisons, which places its worst-case and average running time in O(n²) in Big O notation. Doubling the input size therefore roughly quadruples the work, which is why the algorithm becomes slow well before inputs reach the sizes typical of real applications.
| Case | Input shape | Comparisons | Time complexity |
|---|---|---|---|
| Best case | Already sorted, with early exit | n − 1 | O(n) |
| Average case | Random order | About n²/2 | O(n²) |
| Worst case | Reverse sorted | n(n − 1)/2 | O(n²) |
| Space | Any input | Not applicable | O(1) extra memory |
The number of swaps equals the number of inversions in the input, meaning pairs of elements that are out of order. A reverse-sorted list has the maximum of n(n − 1)/2 inversions, so it also needs the maximum number of swaps. The algorithm sorts in place, needing only a constant amount of extra memory for a temporary value and a flag.
Key properties: stability, adaptivity and in-place sorting
Bubble sort has three properties that matter when comparing sorting algorithms. It is stable, because it swaps only when the left element is strictly greater, so equal elements keep their original relative order. It is in place, and with the early-exit flag it is adaptive, running faster on inputs that are nearly sorted.
Adaptivity has an important limit. A small element near the end of the list moves only one position toward the front per pass, a pattern often called a turtle, while large elements near the front move quickly, called rabbits. A list that is sorted except for one small value at the end can therefore still need nearly n passes.
- Cocktail shaker sort alternates forward and backward passes so that turtles also move quickly.
- Comb sort compares elements a shrinking gap apart before finishing with adjacent comparisons.
- Odd-even transposition sort compares disjoint pairs in parallel, which suits some parallel hardware.
Bubble sort compared with other sorting algorithms
Compared with its neighbors, bubble sort is simple but slow. Even among quadratic algorithms it usually performs the most swaps, while divide and conquer algorithms such as merge sort and quicksort reach O(n log n) on typical inputs.
| Algorithm | Average time | Stable | Extra space | Typical role |
|---|---|---|---|---|
| Bubble sort | O(n²) | Yes | O(1) | Teaching, tiny inputs |
| Insertion sort | O(n²) | Yes | O(1) | Small or nearly sorted data |
| Selection sort | O(n²) | No | O(1) | Minimizing number of writes |
| Merge sort | O(n log n) | Yes | O(n) | Stable sorting of large data |
| Quicksort | O(n log n) | No | O(log n) | General-purpose in-memory sorting |
In practice, insertion sort beats bubble sort on almost every input of the same size, because it shifts elements instead of swapping them repeatedly. This is why hybrid library sorts use insertion sort, not bubble sort, for short subarrays.
Where bubble sort is still useful and its pitfalls
Bubble sort remains valuable mainly as a teaching tool for loops, swaps, invariants and complexity analysis. It can also be acceptable for very small fixed-size arrays in constrained environments, where code size matters more than speed, though insertion sort is usually still the better choice.
| Mistake | Consequence | Correction |
|---|---|---|
| Inner loop runs to the end every pass | Redundant comparisons | Shrink the range after each pass |
| No early-exit flag | Sorted input still costs O(n²) | Stop when a pass makes no swaps |
| Using greater or equal in the comparison | Algorithm loses stability | Swap only when strictly greater |
| Off-by-one index bounds | Out-of-range access | Compare up to the last unsorted pair |
The decisive recommendation is simple: use the language’s built-in sort for real data. Implementing bubble sort is worthwhile for understanding how sorting works, not for performance.
Understanding it simply
Bubble sort puts things in order by looking at two neighbors at a time. If the left one is bigger than the right one, they swap places. Then the method moves one step along and repeats.
Picture children lining up by height. The teacher walks along the line and swaps any two neighbors who stand in the wrong order. After one walk, the tallest child has reached the end. The teacher keeps walking until nobody needs to swap. The key takeaway is that the method is easy to understand but becomes very slow for long lines.
Applied in practice
A computer science instructor introduces sorting to a class of first-year students. Each student writes bubble sort for an array of 10 integers, then adds a counter for comparisons and swaps and runs it on sorted, random and reverse-sorted inputs.
The students observe that the sorted array finishes after 9 comparisons with the early-exit flag, while the reversed array needs 45 comparisons and 45 swaps. They then repeat the test with 10,000 elements and compare the timing with the built-in library sort, which finishes far faster. The outcome is a concrete, memorable understanding of quadratic growth and of why efficient algorithms matter.