Bubble sort
easyEach pass carries the largest remaining value to the right. Simple, stable, and slow - but the early-exit check turns the best case into a single linear pass, which is worth understanding before dismissing it.
O(n)Average O(n²)Worst O(n²)Space O(1)StableIn placeSaved in this browser - no sign-up, nothing sent anywhere.
How bubble sort works
Walk the array left to right, compare each pair of neighbours, and swap whenever the left one is larger. One pass carries the largest remaining value all the way to the right end - it bubbles past everything smaller. That makes the last position final after pass 1, the last two after pass 2, and the whole array sorted after at most n passes.
This implementation keeps a swapped flag: when a complete pass makes no swaps, no pair is out of order and the sort stops. That early exit is the entire best case - a sorted 16-element array costs one 15-comparison pass instead of the 120 a flag-free version always pays. The inner loop also shrinks by one each pass, skipping the finished suffix.
Reach for it to learn invariants and stability, not to sort real data - insertion sort does the same quadratic job with roughly half the writes. It is stable because the comparison is strictly a[j] > a[j+1]: equal neighbours never swap, so equal values keep their original order across the whole run.
Step by step
- Sort [5, 3, 8, 4, 6]. Pass 1 compares four neighbour pairs, walking left to right.
- 5 > 3, so they swap: [3, 5, 8, 4, 6]. Then 5 and 8 are already in order.
- 8 > 4 and 8 > 6 - two more swaps carry 8 to the end: [3, 5, 4, 6, 8]. The largest value is final.
- Pass 2 covers the first four slots: 3, 5 stay; 5 > 4 swaps to [3, 4, 5, 6, 8]; 5, 6 stay. Now 6 is final too.
- Pass 3 compares 3, 4 and then 4, 5 - no swaps anywhere, so the swapped flag is still false.
- The early exit fires: sorted in 9 comparisons and 4 swaps, against the 10 comparisons every pass-counting version of this input would pay.
Complexity
| Best case time | O(n) |
|---|---|
| Average time | O(n²) |
| Worst case time | O(n²) |
| Space | O(1) |
n passes over up to n elements; the early exit gives the linear best case.
Reference implementation
Python
def bubble_sort(a):
n = len(a)
for i in range(n):
swapped = False
for j in range(n - i - 1):
if a[j] > a[j + 1]:
a[j], a[j + 1] = a[j + 1], a[j]
swapped = True
if not swapped: # nothing moved - we are done
break
return aJavaScript
function bubbleSort(a) {
const n = a.length;
for (let i = 0; i < n; i++) {
let swapped = false;
for (let j = 0; j < n - i - 1; j++) {
if (a[j] > a[j + 1]) {
[a[j], a[j + 1]] = [a[j + 1], a[j]];
swapped = true;
}
}
if (!swapped) break; // nothing moved - we are done
}
return a;
}Java
static void bubbleSort(int[] a) {
int n = a.length;
for (int i = 0; i < n; i++) {
boolean swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (a[j] > a[j + 1]) {
int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
swapped = true;
}
}
if (!swapped) break; // nothing moved - we are done
}
}C++
void bubbleSort(vector<int>& a) {
int n = a.size();
for (int i = 0; i < n; i++) {
bool swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (a[j] > a[j + 1]) {
swap(a[j], a[j + 1]);
swapped = true;
}
}
if (!swapped) break; // nothing moved - we are done
}
}Worth noticing
The largest value reaches the end after one pass
Each pass carries the biggest remaining value all the way right, which is why the green sorted region grows from the right by exactly one element per pass. Everything else about bubble sort follows from that.
The early exit is the whole best case
Turn the early-exit switch off and run a sorted array: the comparison count jumps to n²/2 even though nothing ever moves. With it on, one clean pass and it stops - O(n).
It is stable, and that is not an accident
The comparison is strictly `>`, so equal values never swap and keep their original order. Change it to `>=` and bubble sort silently stops being stable.
Common pitfalls
- Running the inner loop to the end every pass instead of stopping at n - i - 1 - still correct, but it re-checks the sorted suffix and roughly doubles the comparisons.
- Skipping the swapped flag. Without it a sorted array still costs about n²/2 comparisons; with it, one linear pass. The toggle in this visualizer shows the exact gap.
- Comparing with >= instead of >. The sort still produces sorted output, but equal values now swap past each other and stability is silently gone.
- Letting the inner index reach n - i - 1: the body reads a[j + 1] one slot past the live region - an off-by-one that only bites on the final pair.
- Using it beyond toy sizes: 10,000 values mean around 50 million comparisons, where an O(n log n) sort needs roughly 130,000.
Where it is used
- The classroom introduction to sorting - loop invariants, stability, and best versus worst case in a dozen lines.
- A cheap is-this-sorted check: one pass with no swaps proves order in O(n), which is exactly what the early exit tests.
- Keeping an almost-ordered list tidy between frames - old graphics code re-bubbled polygon depth orders because each frame barely changes.
- The interview warm-up: derive n(n-1)/2, explain the early exit, and say precisely why it is stable.
Frequently asked questions
What is the time and space complexity of bubble sort?
Best case O(n) - the early exit stops after one clean pass over sorted input. Average and worst case O(n²): up to n passes over up to n elements, so 16 reversed values cost 120 comparisons and 120 swaps. Space is O(1) - it sorts in place with two indices and a flag.
Why is bubble sort O(n squared)?
Pass i makes n - i - 1 comparisons, and there can be n - 1 passes. The sum 15 + 14 + ... + 1 is n(n-1)/2, which grows with the square of n - doubling the array quadruples the work. Only the early exit on already-ordered input escapes that arithmetic.
Is bubble sort stable?
Yes. Neighbours swap only when the left one is strictly greater, so two equal values can never trade places - the one that started first stays first. Change the comparison to >= and that guarantee disappears while the output still looks sorted, which is why the strictness matters.
Is bubble sort ever better than insertion sort?
Practically no. Both are O(n²) and both finish early on sorted input, but insertion sort moves each displaced element with one write while a bubble swap costs two. The one thing bubble sort does neatly is double as a sortedness check - a single no-swap pass is a proof.