SortingAlgorithmaka sinking sort, exchange sort

Bubble Sort

Repeatedly swap adjacent out-of-order pairs so the largest remaining element bubbles to the end each pass.

▶ VisualizePattern: Two PointersPractice (1)
Progress

Overview

Bubble sort makes repeated passes over the array, comparing each adjacent pair and swapping when the left is larger. After pass i, the i largest elements sit in their final positions at the end. It is stable, in-place, and with an early-exit flag adaptive — a sorted array costs one O(n) pass.

It is almost never used in production: Insertion Sort does the same O(n²) job with far fewer writes and better cache behaviour. Bubble sort survives as a teaching device for the concepts of passes, invariants, and stability, and as the number of swaps it performs equals the number of inversions in the input.

comparisonO(n²)stablein-placeadaptiveeducational

Intuition

A mental model before the formal terms.

Picture bubbles in a glass of water: on each pass the biggest bubble rises all the way to the surface, because whenever it meets a smaller neighbour they trade places. After each pass one more bubble has settled at the top, and the region still to be sorted shrinks by one.

How it works

  1. For pass i = 0 … n - 2, walk j from 0 to n - 2 - i.
  2. If a[j] > a[j + 1], swap them.
  3. Track whether any swap happened in the pass; if none did, the array is sorted — stop early.
  4. Each pass places the maximum of the unsorted prefix at index n - 1 - i.

Why it works

Invariant after pass i: the last i elements are the i largest, in sorted order. Within a pass, the running maximum is carried right by successive swaps, so it ends at the boundary of the unsorted prefix.

A pass with no swaps means every adjacent pair is ordered, which for a total order implies the whole array is sorted — so early exit is safe.

Each swap removes exactly one inversion, so the swap count equals the inversion count and the algorithm terminates after at most n(n-1)/2 swaps.

Recognition

How to tell a problem wants this.

  • The question is explicitly about bubble sort, stability, or counting adjacent swaps / inversions.
  • "Minimum adjacent swaps to sort" — the answer is the number of inversions, which bubble sort performs exactly.
  • Tiny inputs in a language with no built-in sort where clarity beats speed.
“sorted array” → Two Pointers

Interactive visualization

Play, step, change the input. ← → and space work too.

29
0
10
1
14
2
37
3
13
4
5
5
42
6
21
7
1/54Start with 8 unsorted elements. Each pass bubbles the largest remaining element to the end.
ComparingSwappedIn final position
PseudocodeLearn Bubble Sort →
1for i in 0 .. n-1:
2  swapped = false
3  for j in 0 .. n-i-2:
4    if a[j] > a[j+1]:
5      swap(a[j], a[j+1])
6      swapped = true
7  if not swapped: break
Complexity
best O(n)
avg O(n²)
worst O(n²)
space O(1)
Speed

Pseudocode

1for i from 0 to n - 2:
2  swapped = false
3  for j from 0 to n - 2 - i:
4    if a[j] > a[j + 1]:
5      swap(a[j], a[j + 1]); swapped = true
6  if not swapped: break

Implementations

1def bubble_sort(a: list[int]) -> None:
21 · Setup
3    n = len(a)
42 · Outer pass loop
5    for i in range(n - 1):
6        swapped = False
73 · Compare and swap adjacent pairs
8        for j in range(n - 1 - i):
9            if a[j] > a[j + 1]:  # strict '>' keeps equal keys in order (stable)
10                a[j], a[j + 1] = a[j + 1], a[j]
11                swapped = True
124 · Early exit when no swaps happened
13        if not swapped:
14            break
Walkthrough
  1. range(n - 1 - i) yields the indices of the still-unsorted prefix; it is empty on n <= 1, so no special case is needed.
  2. Tuple swap a[j], a[j + 1] = a[j + 1], a[j] builds and unpacks a tuple; CPython optimises the 2-element case into rotating the stack.
  3. Strict > preserves stability.
  4. break on a swap-free pass gives O(n) on sorted input.
Complexity (this implementation)
time O(n²) worst/average, O(n) best · space O(1)

Pure-Python loops are ~50-100x slower than list.sort() (C TimSort); use this only to learn.

Language notes
  • list.sort() sorts in place and returns None; sorted(a) returns a new list. Both are stable TimSort.
  • Use key= rather than cmp_to_key for custom orders; keys are computed once per element.
  • Type hint list[int] needs Python 3.9+; use List[int] from typing on older versions.
Common mistakes in this language
  • Writing a = a.sort() — assigns None.
  • Using >=, which breaks stability.
  • Iterating for j in range(n - 1) on every pass instead of shrinking by i.
Language differences that matter here
  • JS/TS [10, 2, 5].sort() yields [10, 2, 5] because the default comparator converts to strings; pass (x, y) => x - y. C++ std::sort and Python sort compare numerically by default.
  • Stability of library sorts: std::sort is unstable (introsort), std::stable_sort is stable; Array.prototype.sort is stable since ES2019; Python list.sort/sorted are always stable (TimSort).
  • In-place mutation: C++ needs a non-const reference, JS/TS/Python pass arrays/lists by reference so the caller sees the changes.
  • Swap idiom: std::swap in C++, destructuring in JS/TS (may allocate), tuple unpacking in Python (optimised by CPython).

Complexity

Best
O(n)
Average
O(n²)
Worst
O(n²)
Space
O(1)

Best case requires the early-exit flag. Swaps = number of inversions. Stable, in-place, adaptive.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Teaching passes, invariants, and stability.
  • Detecting whether an array is already sorted, or nearly sorted, with one cheap pass.
  • Counting adjacent swaps needed to sort (equals inversions) on small inputs.
Avoid it when

Alternatives

Insertion SortSelection SortMerge SortQuick Sort

Common mistakes

  • Iterating the inner loop to n - 1 on every pass instead of shrinking by i, doubling the work.
  • Omitting the swapped flag and losing the O(n) best case.
  • Using >= in the comparison, which swaps equal elements and breaks stability.

Interview patterns

  • Explain stability with a concrete example of two equal keys and show why > (not >=) preserves order.
  • Count inversions: bubble sort in O(n²), then improve to O(n log n) with a modified merge sort.
  • Cocktail shaker sort variant: alternate directions to fix "turtles" (small elements at the end).
Interview questions on this
Mock interviews

Example problems

Sort Colors (Dutch National Flag)medium