vault

Bubble Sort

19 min read

Bubble Sort

Bubble sort is the canonical pedagogical example of a comparison sort: walk the array, compare every adjacent pair, swap any that are out of order, repeat until a full pass produces no swaps. The “bubble” metaphor is that on each pass the largest still-unplaced element rises to its final position the way a bubble rises through water. Time complexity is Θ(n²) average and worst, with a Θ(n) best case only when an early-exit flag is added to detect a no-swap pass on already-sorted input. Bubble sort is in-place (Θ(1) auxiliary space), is one of the few comparison sorts that is naturally stable, and has the unusual property that the bound on the number of swaps equals the number of inversions in the input — a fact that makes bubble sort show up in proofs about sortedness even though the algorithm itself is essentially never used in production. The famous interview-folklore question “what’s wrong with bubble sort?” is really a question about algorithmic literacy: candidates who say “nothing, it sorts!” are signaling that they conflate correctness with efficiency, while candidates who unpack the Θ(n²) time, the lack of cache locality benefit over Insertion Sort, and the existence of dramatically better simple sorts are signaling the opposite. Every line of this note is, indirectly, an answer to that question.

1. Intuition — The Bubble Rising

Imagine a tall glass column of water with bubbles of various sizes scattered through it. The bubbles are buoyant, but only one bubble can pass another bubble at a time, and only between immediately neighboring bubbles. So you walk a finger up the column from bottom to top, and at each pair of adjacent bubbles you swap them if the smaller one is below the larger one (smaller bubbles rise faster, so the smaller-below-larger configuration is “wrong”). After one full bottom-to-top sweep, the smallest bubble has risen one notch above the bottom (or the largest has sunk to the bottom, depending on which way you frame the comparison). After a second sweep, the next-smallest has joined the front, and so on. After n − 1 sweeps the entire column is sorted by size.

The classical formulation of bubble sort actually inverts this metaphor: instead of small bubbles rising, the largest unsorted element “bubbles” to the end of the array on each pass. The two framings are equivalent — pick whichever direction makes the comparison arr[j] > arr[j+1] mentally easier — but the “largest sinks to the right” version is more common in textbooks because it matches the standard for j := 0 to n − 2 − k pass shape, where the last k slots already hold sorted elements after k passes.

The conceptual reason bubble sort is wasteful is that it only makes one element of progress per linear pass: the most-out-of-place element from one end migrates to its correct end-position by being walked across the array one swap at a time. That is Θ(n) work per pass, Θ(n) passes, hence Θ(n²). By contrast, Insertion Sort also does Θ(n) work per pass in the worst case, but on partially-sorted input each pass terminates early, giving Θ(n) best-case time — bubble sort gets the same best case only with the explicit early-exit flag.

2. Tiny Worked Example (n = 5)

Sort [5, 2, 8, 1, 4] using bubble sort with the standard “largest sinks right” formulation. After pass k, the last k slots hold the k largest values in sorted order, so we only need to scan up to index n − 1 − k.

Pass 1 (k = 1, scan indices 0..3)

[5, 2, 8, 1, 4]
 ↑
Compare 5,2: 5 > 2, swap → [2, 5, 8, 1, 4]
Compare 5,8: 5 < 8, no swap
Compare 8,1: 8 > 1, swap → [2, 5, 1, 8, 4]
Compare 8,4: 8 > 4, swap → [2, 5, 1, 4, 8]

After pass 1: [2, 5, 1, 4, | 8] — 8 is in its final position. Three swaps occurred.

Pass 2 (k = 2, scan indices 0..2)

Compare 2,5: 2 < 5, no swap
Compare 5,1: 5 > 1, swap → [2, 1, 5, 4, 8]
Compare 5,4: 5 > 4, swap → [2, 1, 4, 5, 8]

After pass 2: [2, 1, 4, | 5, 8] — 5 is in its final position. Two swaps.

Pass 3 (k = 3, scan indices 0..1)

Compare 2,1: 2 > 1, swap → [1, 2, 4, 5, 8]
Compare 2,4: 2 < 4, no swap

After pass 3: [1, 2, | 4, 5, 8] — 4 is in its final position. One swap.

Pass 4 (k = 4, scan index 0..0)

Compare 1,2: 1 < 2, no swap

After pass 4: [| 1, 2, 4, 5, 8] — zero swaps. The early-exit flag would set swapped = false here and terminate. Without the flag, the algorithm would continue (here, no further passes are scheduled because k = n − 1).

Final array: [1, 2, 4, 5, 8].

Two observations to internalize:

  1. The total number of swaps (3 + 2 + 1 + 0 = 6) equals the number of inversions in the input. An inversion is any pair (i, j) with i < j and arr[i] > arr[j]; counting them in [5, 2, 8, 1, 4] gives exactly 6 ((5,2), (5,1), (5,4), (8,1), (8,4), (2,1)). This is not a coincidence — see the complexity discussion in §5.
  2. Pass 4 does work even though the array is already sorted. Without the swapped flag, bubble sort makes a wasted scan; with the flag, it can detect the no-swap pass and exit, achieving the Θ(n) best case on sorted input.

3. Pseudocode

3.1 Naïve form (no early-exit)

bubble_sort_naive(arr):
    n := length(arr)
    for k := 1 to n − 1:
        for j := 0 to n − 1 − k:
            if arr[j] > arr[j + 1]:
                swap arr[j], arr[j + 1]

This always does exactly (n − 1) + (n − 2) + … + 1 = n(n − 1)/2 comparisons regardless of input — like vanilla Selection Sort, it has no shortcut and no Θ(n) best case.

3.2 With the early-exit flag (the version interviewers want)

bubble_sort(arr):
    n := length(arr)
    for k := 1 to n − 1:
        swapped := false
        for j := 0 to n − 1 − k:
            if arr[j] > arr[j + 1]:
                swap arr[j], arr[j + 1]
                swapped := true
        if not swapped:
            return                  # array is sorted; exit early

The flag adds one boolean and one branch per outer-loop iteration — negligible overhead. In return, the algorithm runs in Θ(n) on already-sorted input (one full pass with zero swaps, then the flag triggers the early return).

4. Python Implementation

def bubble_sort(arr: list[int]) -> None:
    """In-place ascending bubble sort with early-exit flag.
    Stable: YES. Adaptive: YES (with the flag)."""
    n = len(arr)
    for k in range(1, n):
        swapped = False
        for j in range(n - k):                  # last k elements already sorted
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            return                              # short-circuit on sorted input

A few implementation notes worth narrating in an interview. First, the inner-loop upper bound n − k (Python range(n − k) walks j from 0 to n − k − 1, so the comparison is between arr[j] and arr[j + 1], i.e., the last comparison is between arr[n − k − 1] and arr[n − k]) is the standard “shrink the unsorted region by one each pass” optimization — without it, every pass would scan the entire array, doubling the constant factor. Second, the > (strict) in the comparison preserves stability: equal elements never trigger a swap, so their relative order is preserved (see §7). Third, the early return on not swapped is the difference between Θ(n²) always and Θ(n) best — a free optimization that every textbook variant should have but that surprisingly many candidates omit.

5. Complexity Analysis

5.1 Time

Worst case (reverse-sorted input, e.g., [5, 4, 3, 2, 1]): every comparison results in a swap, every pass does the maximum work. The pass-k inner loop runs n − k times, summed over k = 1..n − 1:

T_worst(n) = Σ_{k=1}^{n−1} (n − k) = (n − 1) + (n − 2) + … + 1 = n(n − 1)/2 = Θ(n²)

where:

  • Σ_{k=1}^{n−1} is a sum over outer-loop iterations.
  • n − k is the number of comparisons in pass k (the unsorted region shrinks by one each pass).
  • The closed form n(n − 1)/2 is the standard arithmetic-series sum.

Best case (already-sorted input, with the early-exit flag): pass 1 makes n − 1 comparisons, all of which pass (arr[j] ≤ arr[j + 1]), so swapped stays false, and the algorithm exits. Total: n − 1 comparisons, 0 swaps, Θ(n). Without the flag, the best case is Θ(n²) because the outer loop blindly continues for n − 1 iterations.

Average case (random permutation): both rigorous analysis (Knuth, TAOCP §5.2.2) and the inversion-count interpretation give Θ(n²). Specifically, the expected number of swaps for a uniformly random permutation of n distinct elements equals the expected number of inversions, which is n(n − 1)/4 — half the maximum.

5.2 The Inversion-Count Identity

A beautiful and useful invariant: the total number of swaps performed by bubble sort equals the number of inversions in the input array, where an inversion is a pair of indices (i, j) with i < j and arr[i] > arr[j].

The proof sketch: bubble sort only swaps adjacent elements, and each adjacent swap removes exactly one inversion (the swapped pair) without creating any other inversion (the swap is local, so it does not affect the relative order of any pair of non-adjacent elements). The array is sorted iff there are no inversions. Therefore the number of swaps must equal the starting number of inversions.

This identity is the key reason bubble sort still appears in theoretical contexts: it gives a constructive proof that n(n − 1)/2 is the maximum possible number of inversions in any permutation of n distinct elements, and it provides an O(n²)-time inversion counter that is conceptually simpler than the O(n log n) counter via Merge Sort. In production you would always use the merge-sort counter for inversions, but in proofs the bubble-sort counter is often pedagogically clearer.

5.3 Space

Auxiliary space is Θ(1) — a constant number of scalar variables (loop indices, the swapped flag, the swap temp). No recursion, no auxiliary array. Bubble sort is truly in-place.

6. Variants

6.1 Cocktail Shaker Sort (Bidirectional Bubble Sort)

Each “pass” actually consists of two sub-passes: a left-to-right sweep that bubbles the largest unsorted element to the right end, followed by a right-to-left sweep that bubbles the smallest unsorted element to the left end. Then the unsorted region shrinks from both ends.

cocktail_sort(arr):
    n := length(arr)
    lo, hi := 0, n - 1
    while lo < hi:
        swapped := false
        for j := lo to hi - 1:
            if arr[j] > arr[j + 1]:
                swap arr[j], arr[j + 1]
                swapped := true
        if not swapped: return
        hi := hi - 1
        for j := hi - 1 down to lo:
            if arr[j] > arr[j + 1]:
                swap arr[j], arr[j + 1]
                swapped := true
        if not swapped: return
        lo := lo + 1

Cocktail shaker sort fixes one specific bubble-sort weakness called the turtle problem: a small element near the end of the array (a “turtle”) moves only one position toward the front per left-to-right pass — slowly. Bidirectional sweeping moves turtles backward at full speed in the right-to-left passes, halving the number of passes on inputs where small elements are clustered at the tail. The asymptotic bound is unchanged (Θ(n²) average and worst), but the constant factor improves on certain input distributions. Cocktail shaker is also stable and adaptive in the same senses as plain bubble sort.

6.2 Comb Sort

Comb sort generalizes bubble sort by comparing elements at a gap greater than 1 (initially gap ≈ n / 1.3), shrinking the gap each pass until it reaches 1, at which point the algorithm becomes ordinary bubble sort. The larger initial gap fixes the turtle problem aggressively. Comb sort is essentially what Shell Sort is to Insertion Sort — a gap-based generalization that recovers O(n log² n)-ish empirical performance from a Θ(n²) base. Stability is lost because gap-based swaps are non-adjacent.

6.3 Odd–Even Sort (Brick Sort)

Alternates between comparing all even-indexed adjacent pairs (0,1), (2,3), (4,5), … and all odd-indexed adjacent pairs (1,2), (3,4), (5,6), …. The structural advantage is that both phases are fully parallelizable (no two pair-comparisons in the same phase share an index), making this variant interesting on parallel-processor architectures. Sequential complexity is still Θ(n²); parallel complexity is O(n) with O(n) processors.

7. Stability and Adaptiveness

Stable: Yes. The strict > comparison in the swap test ensures that two equal elements never swap with each other. Their relative order in the input is therefore preserved through every pass. Bubble sort is one of the few stable comparison sorts that does not require auxiliary memory.

Adaptive: Yes (with the early-exit flag). On already-sorted input the algorithm runs in Θ(n); on nearly-sorted input the outer loop terminates after a small number of passes once a no-swap pass occurs. Without the flag bubble sort is non-adaptive — Θ(n²) always — which is why every responsible implementation includes the flag and why interview answers should mention it explicitly.

A subtle point: even with the flag, bubble sort is less adaptive than Insertion Sort. If the input is “one element out of place” (e.g., [2, 3, 4, 5, 1]), insertion sort runs in Θ(n) because each element after 1 shifts only when 1 is finally inserted, while bubble sort runs in Θ(n) per pass and needs Θ(n) passes to drift 1 to the left end — Θ(n²) total. The flag only short-circuits fully sorted prefixes, not partially-sorted regions.

8. Why Bubble Sort Is Never Used in Production

This is the meat of the famous interview question. Several reasons stack up:

  1. It is dominated by Insertion Sort on every metric, including ones where bubble sort might naïvely look competitive. Insertion sort has the same Θ(n²) worst case, the same Θ(n) best case, the same Θ(1) aux space, the same stability — and a smaller constant factor (Knuth measures roughly half the average comparisons), better adaptivity on partially-sorted inputs, and better cache behavior because its inner loop is purely a backward scan with predictable memory access. There is no input distribution on which bubble sort beats insertion sort by a meaningful margin.
  2. It is dominated by Selection Sort on the write-count metric. Bubble sort can perform up to n(n − 1)/2 swaps in the worst case (one per inversion); selection sort is bounded at n − 1. So on write-asymmetric storage where selection sort would shine, bubble sort is the worst possible choice.
  3. Its branch behavior is bad on modern CPUs. Every adjacent comparison is a data-dependent branch, and pathologically random data causes the branch predictor to mispredict ~50 % of the time, stalling the pipeline. Insertion sort has more predictable branches because the inner loop’s exit condition is monotonic over each element’s insertion.
  4. It is only slightly easier to implement than insertion sort, so the “simplicity” defence does not really hold.

The pedagogical value of bubble sort is not that anyone should implement it, but that its analysis is the easiest path into loop-invariant reasoning, the inversion-count identity, and the broader question of how comparison sorts can or cannot beat Θ(n²). Owen Astrachan’s SIGCSE 2003 paper Bubble Sort: An Archaeological Algorithmic Analysis makes the strong argument that bubble sort should be removed from introductory CS curricula in favour of insertion sort, on the grounds that bubble sort is harder to analyze and worse on every realistic input — yet bubble sort persists in textbooks largely because of inertia.

A note on the auto-vectorization angle: it might be tempting to hope that modern compilers (LLVM’s Loop Vectorizer, GCC’s -ftree-vectorize) rescue bubble sort by SIMD-widening its inner loop. They do not, and structurally cannot. LLVM’s Loop Vectorizer documentation is explicit that it widens loops “to operate on multiple consecutive iterations” only when iterations are independent (LLVM Vectorizers docs). Bubble sort’s inner loop carries a hard data dependency across iterations — the swap at (j, j+1) modifies arr[j+1], which is the left operand of the next iteration’s comparison at (j+1, j+2). That cross-iteration dependence is precisely what stops SIMD widening. Insertion sort shares the same obstruction in its naïve form (the shift loop is sequential), but the constant-factor and branch-prediction wins documented above still hold; auto-vectorization is not the lever that closes the gap.

9. Pitfalls

  1. Omitting the early-exit flag. Without swapped, the algorithm runs in Θ(n²) even on already-sorted input — a concrete and easily-spotted interview red flag.
  2. Off-by-one in the inner-loop upper bound. Writing for j := 0 to n − 1 instead of for j := 0 to n − 1 − k makes the algorithm correct but doubles the constant factor (it scans into the already-sorted suffix). Worse, writing for j := 0 to n causes an array-out-of-bounds access on arr[j + 1].
  3. Using ≥ instead of > in the swap test. This breaks stability — equal elements get swapped, reversing their relative order. The test must be strict > for stability.
  4. Claiming Θ(n) average case. A common confusion is to assume the early-exit flag makes the average case linear. It does not — average-case input has roughly n²/4 inversions, so Θ(n²) swaps and passes are still required. Only the best case (truly sorted input) hits Θ(n).
  5. Using bubble sort on linked lists. Bubble sort is built around adjacent-swap primitives, which on a linked list cost Θ(1) per swap (just relink pointers). However, the Θ(n²) time is unchanged, and on a linked list Merge Sort runs in Θ(n log n) while preserving the list structure with no random access — strictly better.

10. Diagram

flowchart TD
  Start["Input: [5, 2, 8, 1, 4]"] --> P1["Pass 1<br/>scan 0..3<br/>3 swaps"]
  P1 --> S1["[2, 5, 1, 4 | 8]<br/>'8' fixed at end"]
  S1 --> P2["Pass 2<br/>scan 0..2<br/>2 swaps"]
  P2 --> S2["[2, 1, 4 | 5, 8]<br/>'5' fixed"]
  S2 --> P3["Pass 3<br/>scan 0..1<br/>1 swap"]
  P3 --> S3["[1, 2 | 4, 5, 8]<br/>'4' fixed"]
  S3 --> P4["Pass 4<br/>scan 0..0<br/>0 swaps"]
  P4 --> S4["[| 1, 2, 4, 5, 8]<br/>swapped=false → exit"]

What this diagram shows. The pass-by-pass evolution of bubble sort on the example input [5, 2, 8, 1, 4]. The vertical bar | marks the boundary between the unsorted prefix and the already-sorted suffix; on each pass the boundary moves one slot to the left because the largest remaining unsorted element bubbles into the suffix. The number of swaps per pass (3, 2, 1, 0) decreases monotonically because each pass eliminates at least one inversion of the maximum element; in general the sum of swaps across all passes equals the input’s inversion count (here, 6). Pass 4’s “0 swaps” triggers the early-exit flag, terminating the algorithm one pass earlier than the naïve n − 1 outer-loop bound — this is the only mechanism that gives bubble sort its Θ(n) best case.

11. Common Interview Problems

ProblemSourceWhy bubble sort comes up
Implement bubble sortClassic warm-up / 1st-week-of-CSLoop-invariant reasoning, swap mechanics, the early-exit optimization
Count inversions in an arrayLeetCode 493 (Reverse Pairs), CTCIBubble sort gives a conceptually simple O(n²) solution; production answer uses Merge Sort for O(n log n)
”Sort with minimum number of adjacent swaps”Several CP problemsThe minimum number of adjacent swaps to sort an array equals its inversion count, which equals bubble sort’s swap count
Identify the bug in this bubble-sort code”Spot the bug” interview classicOff-by-one in inner-loop bound, missing flag, ≥ vs >
”What’s wrong with bubble sort?”Interview folkloreThe expected answer is the O(n²) time, dominated by insertion sort, plus cache and branch-prediction concerns

The Count Inversions problem (LeetCode 493 and many variants) is the most common context where bubble sort’s analysis genuinely earns its keep — even though the solution is implemented via Merge Sort, the intuition for why the inversion count is the right quantity comes from bubble sort.

12. Open Questions

  • On very small n (say, ≤ 8), does bubble sort’s smaller code size offer any practical advantage on memory-constrained microcontrollers, or does insertion sort always win even there?
  • What is the precise expected number of passes (not swaps) bubble sort makes on a uniformly random permutation? Knuth gives n − √(πn/2) + O(1), but the derivation is non-trivial — verify against a primary source before citing.
  • How does cocktail-shaker sort’s constant-factor improvement scale on real-world “almost sorted” datasets (e.g., insertion-modified sequences from databases)?

13. Production Notes — Where Bubble Sort Actually Lives

The empirical claim is easy to state and easy to verify: no mainstream production sort routine ships bubble sort. The C++ standard library’s std::sort is specified to be O(n log n) since C++11 and is universally implemented as introsort (a quicksort/heapsort/insertion-sort hybrid that falls back to heapsort after a recursion-depth bound to guarantee worst case, and to insertion sort on small partitions); libstdc++‘s __sort and libc++‘s std::sort both follow this template. Java’s Arrays.sort(int[]) uses a Dual-Pivot Quicksort (Yaroslavskiy / Bentley / Bloch), and Arrays.sort(Object[]) and Collections.sort use TimSort, the adaptive merge-sort/insertion-sort hybrid originally designed for CPython. CPython’s list.sort and sorted() are TimSort. Go’s sort.Slice was historically introsort and was changed to pdqsort (pattern-defeating quicksort) in Go 1.19. V8 switched JavaScript’s Array.prototype.sort from quicksort to TimSort in 2018 (V8 release notes). Across every major standard library, the family is the same: a quicksort variant (introsort, dual-pivot, pdqsort) for unstable in-place; TimSort (or near-equivalents) for stable; insertion sort as the small-partition base case. Bubble sort appears nowhere in this family. Its only “production” appearances are in pedagogical demos, embedded toy code, and a handful of niche cases (Wikipedia notes computer graphics polygon-fill on near-sorted lists) where the implementer wants the absolute simplest stable in-place sort and the input is so small that constant factors do not matter. Whenever you see bubble sort in a real codebase, it is almost always either (a) a leftover from a junior implementation that nobody benchmarked, (b) a deliberate “we know n ≤ 8 and don’t care” choice, or (c) a teaching example. In an interview, the empirically correct answer to “do you ever use bubble sort in production?” is no, and here is why — not it depends.

14. See Also

Graph View

Backlinks