How bubble sort works
Bubble sort only ever looks at two neighbours. Walk from left to right; whenever a[j] > a[j + 1], swap them. The largest value is swapped along at every step, so by the end of the pass it has bubbled up to the last index, its final place.
Picture people in a queue sorting themselves by height, where each person may only swap with the one next to them. The tallest person keeps winning swaps and drifts to the back in one walk along the line. A short person at the back, though, moves forward only one place per walk.
Each pass can stop one index earlier, because the end of the array is already final. This page also keeps a swapped flag: if a whole pass makes no swaps, every neighbour pair is in order, so the array is sorted and the loop stops. Without that flag, bubble sort makes n(n − 1)/2 comparisons even on sorted input.
Every swap fixes exactly one pair of values that were out of order, so the number of swaps equals the number of inversions, the same as the number of shifts in insertion sort. The comparison is a strict >, so equal neighbours are never swapped and the sort is stable.
The algorithm in 5 steps
- 1 Set
endto the last index. - 2 Walk
jfrom 0 toend − 1; ifa[j] > a[j + 1], swap them and note that a swap happened. - 3 The largest value of
0..endis now atend, its final place. - 4 If the pass made no swaps, stop: the array is sorted.
- 5 Otherwise move
endone place left and walk again.
Worked example
Here is the full run on a fixed array, generated by the same code as the visualizer. Each row is the end of one pass; the comparisons and swaps inside a pass are counted in the total but not listed. Watch the last row: a pass with no swaps ends the sort early.
Input: [5, 1, 4, 2, 8]
- Step 10 Pass 1 done: 8 has bubbled up to index 4, its final place. 14258
- Step 16 Pass 2 done: 5 has bubbled up to index 3, its final place. 12458
- Step 20 No swaps in pass 3, so indices 0–2 are already in order. Stop early. 12458
Total for this run: 9 comparisons and 4 swaps, in 21 animation steps. Result: 1, 2, 4, 5, 8.
Time and space complexity
Best
O(n)Already sorted input with the swapped flag: one pass of n − 1 comparisons, no swaps, then stop.
Average
O(n²)About n²/4 swaps on random input (one per inversion), and on the order of n²/2 comparisons.
Worst
O(n²)Reverse-sorted input: n − 1 passes, n(n − 1)/2 comparisons and as many swaps.
Space
O(1)One flag and a couple of indices. No extra array, no recursion.
- Stable:
- Yes
- In place:
- Yes
- Early exit:
- Yes (swapped flag)
- Compares:
- Neighbours only
Six sorts, same 8 numbers
Comparison counts from running each algorithm on the visualizer's array, then on the same numbers already sorted and in reverse order. Computed from the code on these pages, not typed in.
| Algorithm | Comparisons | Moves | Sorted input | Reversed input |
|---|---|---|---|---|
| Insertion sort | 17 | 13 shifts | 7 | 28 |
| Selection sort | 28 | 5 swaps | 28 | 28 |
| Bubble sort | 25 | 13 swaps | 7 | 28 |
| Merge sort | 16 | 24 writes | 12 | 12 |
| Quick sort | 38 | 5 swaps | 31 | 32 |
| Heap sort | 26 | 19 swaps | 27 | 24 |
The last two columns are comparisons too. Exact counts depend on the input and the variant (this page's bubble sort stops after a pass with no swaps), which is why complexity is stated as growth, not exact numbers.
When to use it, and when not to
Good fit
- Learning: it is the easiest sort to reason about, and its invariant (after pass k, the last k values are final) is a good first proof.
- Checking whether data is already sorted while fixing small local disorder in the same pass: one pass with no swaps proves the array is sorted.
- Hardware or parallel settings where only neighbours can talk to each other. The parallel variant, odd-even transposition sort, compares and swaps disjoint neighbour pairs at the same time.
Pick something else when
- Almost any real program. On the same O(n²) budget, insertion sort is faster, and your language's built-in sort is O(n log n).
- Data with small values near the end. Each pass moves such a value only one place left, so it needs nearly one pass per position.
- Large arrays: at 100,000 random values it makes about 2.5 billion swaps.
Common mistakes and bugs
-
1.Running the inner loop to the last index
With
for j in range(end + 1)orj < n, the code readsa[j + 1]one past the end. Java throwsArrayIndexOutOfBoundsException, Python throwsIndexError, and JavaScript compares againstundefinedwithout any error. -
2.Forgetting to reset the flag each pass
If
swapped = Falseis set once outside the outer loop, the flag stays true after the first swap and the early exit never fires. Reset it at the start of every pass. -
3.Not shrinking the range
Walking the full array every pass still sorts, but it re-compares the values that are already final at the end: about twice the comparisons for no benefit.
-
4.Using >= instead of >
Swapping equal neighbours keeps the output sorted but breaks stability. On an array of equal values every pass then swaps something, so the early exit never fires.
-
5.Calling it O(n) without the flag
The O(n) best case belongs to the version with the early exit. The plain textbook loop always makes n(n − 1)/2 comparisons, even on sorted input.
Interview questions
Try answering before you open the model answer.
Q1 How would you optimise bubble sort?
Model answer: Stop early when a pass makes no swaps: sorted input then costs one pass. Go further by remembering where the last swap happened; everything after it is already final, so the next pass can end there. Both keep it O(n²) in the worst case, which is why real code uses an O(n log n) sort instead.
Q2 What is the minimum number of adjacent swaps needed to sort an array?
Model answer: The number of inversions: pairs i < j with a[i] > a[j]. Each adjacent swap changes the inversion count by exactly one, and bubble sort only swaps out-of-order neighbours, so it achieves that minimum. Counting them by brute force is O(n²); a modified merge sort counts them in O(n log n).
Q3 Is bubble sort stable? What would break it?
Model answer: Yes, because it swaps neighbours only when a[j] > a[j + 1], so two equal values never pass each other. Changing the test to >= swaps equal neighbours, which reverses their order and makes the sort unstable. It also stops the early exit from ever firing on equal values.
Q4 What are rabbits and turtles in bubble sort?
Model answer: A large value near the start is a rabbit: it can travel all the way to the end in one pass. A small value near the end is a turtle: it moves only one place left per pass. Cocktail shaker sort alternates the direction of passes, and comb sort compares far-apart values first, both to move turtles faster.
Q5 Bubble sort and insertion sort are both O(n²). Why is insertion sort faster?
Model answer: Both make one move per inversion, but insertion sort moves a value with one write (a shift), while bubble sort uses a swap, which is three. Insertion sort also stops each walk as soon as the key is in place, so on random input it makes about half the comparisons of bubble sort.
Frequently asked questions
What is the time complexity of bubble sort?
O(n²) in the average and worst case: a reversed array needs n(n − 1)/2 comparisons and as many swaps. With the early-exit flag used on this page, the best case is O(n): sorted input takes one pass of n − 1 comparisons and stops. Bubble sort needs only O(1) extra space.
Is bubble sort stable?
Yes. It swaps two neighbours only when the left one is strictly bigger, so equal values never pass each other and keep their original order. If the comparison is written as >= instead of >, equal neighbours get swapped and the sort is no longer stable.
Why is bubble sort considered inefficient?
It does O(n²) work on typical input and moves values one place at a time with swaps. Even among simple sorts, insertion sort does the same job with fewer comparisons and cheaper moves. Donald Knuth wrote that bubble sort seems to have nothing to recommend it except a catchy name and some interesting theoretical problems.
What does the swapped flag do in bubble sort?
It records whether the current pass swapped anything. If a full pass makes no swaps, every pair of neighbours is in order, which means the whole array is sorted, so the loop can stop. This turns the best case on sorted input from n(n − 1)/2 comparisons into n − 1.
Should I ever use bubble sort in real code?
Rarely. For real data, call your language's built-in sort, which is O(n log n). Bubble sort is worth knowing for interviews and for its ideas: neighbour swaps, inversions and early exit. Its parallel cousin, odd-even transposition sort, is used where hardware can only compare neighbours.