Bubble sort

The problem it solves

Honestly? Almost none, in production — and pretending otherwise would undercut everything this page teaches. Bubble sort survives because it is the clearest possible answer to a different question: what does sorting even consist of? Its entire mechanism is the smallest legal move — compare two neighbours, swap them if they disagree — repeated until no disagreement remains. Every other comparison sort is a cleverer arrangement of that same move; bubble sort is the move, undisguised.

That makes it the baseline you measure improvement against. When an interviewer asks “why is your algorithm better than bubble sort?”, they are asking whether you can articulate what costs — comparisons, swaps, passes — and which of them your improvement removes. Being precise about the baseline is the actual skill under test.

The intuition — and where it breaks down

Air bubbles in water: the biggest bubble rises fastest, and after one bout of jostling it sits on top. Each left-to-right pass, the largest remaining value wins every comparison it meets and gets carried — swap by swap — to the end of the unsorted region, where it locks permanently. One pass, one guaranteed placement, from the right end inward.

Watch the visualization and the analogy’s failure is immediately visible: big values rocket rightward within a single pass, but small values drift left one position per pass, at most. A tiny element at the far right needs nearly n passes to come home — the classic “turtle”. Real bubbles don’t have a direction where they’re slow; this algorithm does, and that asymmetry (fixed by cocktail-shaker’s alternating passes, a fun but still-quadratic remedy) is a genuinely non-obvious structural fact hidden inside “the simple one”.

Loading…

A walkthrough you can check

Sort [4, 2, 5, 1, 3].

Pass one: 4>2 swap → [2,4,5,1,3]; 4<5 stay; 5>1 swap → [2,4,1,5,3]; 5>3 swap → [2,4,1,3,5]. The 5 — the largest — surfed three swaps to the end. Locked.

Pass two (over the first four only): 2<4 stay; 4>1 swap; 4>3 swap → [2,1,3,4,5]. 4 locked.

Pass three: 2>1 swap → [1,2,3,4,5]. 3 locked — and notice 1 and 2, the turtles, only just arrived.

Pass four: one comparison, no swap — and here is the detail that separates a good implementation from a naive one: a pass with zero swaps proves the array is sorted, because “no neighbours disagree” is literally the definition of sorted. The early-exit flag turns bubble sort from unconditionally quadratic into O(n) on already-sorted input. Run the sorted preset and watch the counters: one clean pass, out.

The invariant

After pass k, the last k positions hold the k largest values, in their final order. The sorted region grows from the right, one element per pass, and the inner loop’s shrinking bound (n − 1 − i) is that invariant cashed in: re-scanning the locked region would be pure waste, and forgetting the − i is the most common transcription bug.

The stability argument lives in one character: swaps happen only on strict greater-than. Equal neighbours never swap, so equal elements can never pass each other, so original order among equals survives. Bubble sort is stable by inaction.

Complexity, derived

Count comparisons: pass one makes n−1, pass two n−2, down to 1 — the sum is n(n−1)/2, so O(n²) comparisons always (without early exit). Swaps are the interesting counter: each swap fixes exactly one inversion (an out-of-order pair), and never creates one, so total swaps = number of inversions in the input. Reversed input has the maximum n(n−1)/2 inversions — run the reversed preset and the swap counter hits it exactly; sorted input has zero, and with the flag, one linear pass certifies it.

That “swaps = inversions” identity also condemns the whole neighbour-swap family: any algorithm that only ever swaps adjacent elements must perform at least one swap per inversion, so it cannot beat O(n²) on average. Escaping quadratic requires long-distance moves — which is precisely what shell sort, quicksort and merge sort add. Bubble sort’s ceiling is a theorem, not an implementation failure.

What people get wrong

Omitting the swapped flag, then claiming O(n) best case. Without the flag the loop structure runs all passes regardless; the best case is O(n²) too. The flag is not an optimization garnish — it is the difference between the two claims.

Scanning the full array every pass. Correct but wasteful, and it advertises that you don’t trust (or didn’t notice) the invariant.

“Bubble sort, but I’ll optimize it later.” In an interview, naming insertion sort instead costs nothing and does strictly less work on every input class; reaching for bubble sort as a practical choice, rather than as a named baseline, reads as unfamiliarity with the alternatives.

Confusing it with cocktail or gnome sort under pressure. They are neighbours-swap variants with different pass structures; if you name a variant, be ready to say what it changes (bidirectional passes; single-walker) and what it doesn’t (the quadratic bound).

Implementation notes across languages

There is deliberately little to say — the algorithm is four lines in any language — so the notes are about honesty of measurement. In Python, the tuple swap a[j], a[j+1] = a[j+1], a[j] is the one idiom worth using. In JavaScript, destructuring swap allocates an array per swap in some engines — inside a quadratic loop, that’s measurable; the three-line temp swap isn’t stylish but is free. In Java/C++, bubble sort is occasionally defensible for tiny fixed-size arrays in hot paths only because branch predictors love its access pattern — and even there, insertion sort usually measures faster. The realest implementation note: every standard library already made this decision for you, and none chose bubble sort.