Sorting · Beginner

Bubble Sort

Adjacent elements swap their way to order — simple, visual, and famously slow.

AverageO(n²)StableYesIn-placeYesComparisonYes

Hands on Interactive visualization

Speed

Step 0 / 0

Comparisons

Swaps

Reads

Writes

Elapsed

0.0s

Frames

Depth

0 / 0

Aux memory

0 B

Implementation Code

export function bubbleSort(a: number[]): number[] {
  const n = a.length;
  for (let i = 0; i < n - 1; i++) {
    let swapped = false;
    // After i passes, the last i slots hold their final values.
    for (let j = 0; j < n - 1 - i; j++) {
      if (a[j] > a[j + 1]) { // strict > keeps equal keys stable
        [a[j], a[j + 1]] = [a[j + 1], a[j]];
        swapped = true;
      }
    }
    if (!swapped) break; // clean pass: already sorted (O(n) best case)
  }
  return a;
}

Big-O Complexity

Best

O(n)

Average

O(n²)

Worst

O(n²)

Space

O(1)

O(n) best case requires the early-exit flag; without it every input costs O(n²).

StableYesIn-placeYesComparisonYesRecursiveNoAdaptiveYesOnlineNo

In production When to use

Education

The canonical first sorting algorithm: every step is visible and the invariant (largest unsorted element bubbles to the end each pass) is easy to verify by eye.

Embedded

On tiny microcontrollers sorting a handful of sensor readings, a five-line loop with zero allocations and zero stack growth can beat pulling in a library sort.

Nearly-sorted checks

With the early-exit flag, a single O(n) pass doubles as an is-sorted check that also repairs one out-of-place element as it scans.

Graphics / Game dev

Historically used for per-frame depth sorting of almost-sorted polygon lists, where each frame needs only a pass or two — though insertion sort does the same job with fewer writes.

Verification

Its simplicity makes it a common reference implementation when property-testing a faster sort: compare outputs against bubble sort on small random inputs.

Trade-offs Strengths & weaknesses

Trivial to implement correctly — hard to get wrong in an interview or on a whiteboard.
Stable: equal keys keep their original order.
In-place with O(1) extra memory and no recursion.
Adaptive with the early-exit flag: O(n) on already-sorted input.
Detects sortedness as a side effect of running.

O(n²) comparisons and, worse, O(n²) writes on average — the most swap-heavy of the quadratic sorts.
Consistently slower in practice than insertion sort, its direct quadratic competitor.
Poor cache behavior relative to work done: every pass rescans the whole unsorted prefix.
No serious production use case that insertion sort does not handle better.
Performance collapses on reverse-sorted input: maximal swaps every pass.

Intuition Mental model

Bubbles rising in a glass

Picture array values as bubbles of different sizes in a vertical glass of water. Each pass, the largest remaining bubble rises past its smaller neighbors until it reaches the surface.

Compare each bubble with the one directly above it (adjacent pair).
If the lower bubble is bigger, they trade places — the big one rises one slot.
By the end of one full pass, the biggest unsorted bubble has surfaced: it is in its final position.
Repeat on the shrinking region below the surfaced bubbles.
If a pass completes with no trades, everything has settled — stop early.

Prep Interview questions

How do you make bubble sort O(n) on already-sorted input?

Track whether any swap occurred in a pass. A clean pass proves the array is sorted, so you can break immediately.

Why is bubble sort stable?

It only swaps when a[j] > a[j+1] — a strict inequality. Equal neighbors are never exchanged, so equal keys never cross each other.

Bubble sort vs insertion sort: same complexity class, so why does insertion sort win in practice?

Count the writes. Insertion sort shifts each element once into place; bubble sort may swap the same element many times per pass. Fewer memory writes plus a tighter inner loop.

What is the invariant after the k-th pass of bubble sort?

The k largest elements occupy their final positions at the end of the array. This is why the inner loop bound shrinks by one each pass.

What is cocktail (bidirectional) bubble sort and what problem does it fix?

Alternating left-to-right and right-to-left passes fixes 'turtles' — small elements near the end that otherwise move only one slot per pass.

Watch out Common bugs

Inner loop scans the full array every pass

Using j < n - 1 instead of j < n - 1 - i re-compares the already-settled suffix. Still correct, but doubles the work and hides the algorithm's invariant.

Off-by-one at the right boundary

Comparing a[j] with a[j+1] while letting j reach n - 1 reads one past the end. The inner bound must exclude the last index, not include it.

Early-exit flag reset in the wrong scope

Declaring swapped outside the outer loop and never resetting it per pass means the flag reflects the whole history, not the current pass, so the early exit never triggers after the first swap.

Using >= instead of > in the swap condition

Swapping on equality destroys stability and performs useless writes. Only swap when the left element is strictly greater.

One screen Cheat sheet

Repeatedly swap adjacent out-of-order pairs; the max floats to the end each pass.

Best O(n) · Avg O(n²) · Worst O(n²) · Space O(1)

Stable, in-place, comparison-based.
After pass k, the last k elements are final — shrink the inner bound.
Early-exit flag gives O(n) best case on sorted input.
Most write-heavy quadratic sort; insertion sort dominates it in practice.
Strict > comparison is what preserves stability.

Pick whenTeaching, visualizing, or sorting a handful of items where clarity beats speed.

Avoid whenAny performance-sensitive path — even among O(n²) sorts, insertion sort is the better default.

Implementation Code

export function bubbleSort(a: number[]): number[] {
  const n = a.length;
  for (let i = 0; i < n - 1; i++) {
    let swapped = false;
    // After i passes, the last i slots hold their final values.
    for (let j = 0; j < n - 1 - i; j++) {
      if (a[j] > a[j + 1]) { // strict > keeps equal keys stable
        [a[j], a[j + 1]] = [a[j + 1], a[j]];
        swapped = true;
      }
    }
    if (!swapped) break; // clean pass: already sorted (O(n) best case)
  }
  return a;
}

In production When to use

Education

The canonical first sorting algorithm: every step is visible and the invariant (largest unsorted element bubbles to the end each pass) is easy to verify by eye.

Embedded

On tiny microcontrollers sorting a handful of sensor readings, a five-line loop with zero allocations and zero stack growth can beat pulling in a library sort.

Nearly-sorted checks

With the early-exit flag, a single O(n) pass doubles as an is-sorted check that also repairs one out-of-place element as it scans.

Graphics / Game dev

Historically used for per-frame depth sorting of almost-sorted polygon lists, where each frame needs only a pass or two — though insertion sort does the same job with fewer writes.

Verification

Its simplicity makes it a common reference implementation when property-testing a faster sort: compare outputs against bubble sort on small random inputs.

Trade-offs Strengths & weaknesses

Trivial to implement correctly — hard to get wrong in an interview or on a whiteboard.
Stable: equal keys keep their original order.
In-place with O(1) extra memory and no recursion.
Adaptive with the early-exit flag: O(n) on already-sorted input.
Detects sortedness as a side effect of running.

O(n²) comparisons and, worse, O(n²) writes on average — the most swap-heavy of the quadratic sorts.
Consistently slower in practice than insertion sort, its direct quadratic competitor.
Poor cache behavior relative to work done: every pass rescans the whole unsorted prefix.
No serious production use case that insertion sort does not handle better.
Performance collapses on reverse-sorted input: maximal swaps every pass.

Intuition Mental model

Bubbles rising in a glass

Picture array values as bubbles of different sizes in a vertical glass of water. Each pass, the largest remaining bubble rises past its smaller neighbors until it reaches the surface.

Compare each bubble with the one directly above it (adjacent pair).
If the lower bubble is bigger, they trade places — the big one rises one slot.
By the end of one full pass, the biggest unsorted bubble has surfaced: it is in its final position.
Repeat on the shrinking region below the surfaced bubbles.
If a pass completes with no trades, everything has settled — stop early.

Prep Interview questions

How do you make bubble sort O(n) on already-sorted input?

Track whether any swap occurred in a pass. A clean pass proves the array is sorted, so you can break immediately.

Why is bubble sort stable?

It only swaps when a[j] > a[j+1] — a strict inequality. Equal neighbors are never exchanged, so equal keys never cross each other.

Bubble sort vs insertion sort: same complexity class, so why does insertion sort win in practice?

Count the writes. Insertion sort shifts each element once into place; bubble sort may swap the same element many times per pass. Fewer memory writes plus a tighter inner loop.

What is the invariant after the k-th pass of bubble sort?

The k largest elements occupy their final positions at the end of the array. This is why the inner loop bound shrinks by one each pass.

What is cocktail (bidirectional) bubble sort and what problem does it fix?

Alternating left-to-right and right-to-left passes fixes 'turtles' — small elements near the end that otherwise move only one slot per pass.

Watch out Common bugs

Inner loop scans the full array every pass

Using j < n - 1 instead of j < n - 1 - i re-compares the already-settled suffix. Still correct, but doubles the work and hides the algorithm's invariant.

Off-by-one at the right boundary

Comparing a[j] with a[j+1] while letting j reach n - 1 reads one past the end. The inner bound must exclude the last index, not include it.

Early-exit flag reset in the wrong scope

Declaring swapped outside the outer loop and never resetting it per pass means the flag reflects the whole history, not the current pass, so the early exit never triggers after the first swap.

Using >= instead of > in the swap condition

Swapping on equality destroys stability and performs useless writes. Only swap when the left element is strictly greater.

One screen Cheat sheet

Repeatedly swap adjacent out-of-order pairs; the max floats to the end each pass.

Best O(n) · Avg O(n²) · Worst O(n²) · Space O(1)

Stable, in-place, comparison-based.
After pass k, the last k elements are final — shrink the inner bound.
Early-exit flag gives O(n) best case on sorted input.
Most write-heavy quadratic sort; insertion sort dominates it in practice.
Strict > comparison is what preserves stability.

Pick whenTeaching, visualizing, or sorting a handful of items where clarity beats speed.

Avoid whenAny performance-sensitive path — even among O(n²) sorts, insertion sort is the better default.