Bubble Sort

Overview

What this concept solves

Bubble sort is the first sort you learn and the first sort you should stop using. It compares each pair of adjacent values and swaps them if they're in the wrong order. After one pass the biggest value sits at the end. After two passes the two biggest sit at the end. After n-1 passes everything is sorted. The whole thing is a single nested loop and four lines of code — which is exactly why it's still the entry-point algorithm in every textbook.

It earns its name because large values appear to bubble up (or rather, swim to the right) one slot per pass. Each pass moves the next-largest unsorted value into its final sorted slot at the end. The algorithm only ever swaps neighbours — so a value that needs to travel a long way takes one pass per slot it moves.

The only practical optimization is the early-exit flag: if a full pass completes with zero swaps, the list is already sorted and you can stop. That brings the best case down to O(n). The worst and average case stay at O(n²), which is why bubble sort is essentially useless for n > a few hundred. It's here because the swap idea is the seed of selection, insertion, and quick sort — three algorithms you will use.

Mechanics

How it works

One pass

Start with i = 0. Compare a[i] and a[i+1].
If a[i] > a[i+1], swap them. Otherwise leave them alone.
Advance i. Repeat until you've compared every adjacent pair.
At the end of the pass, the largest value in the unsorted region sits in its final slot at the right.

Across all passes

Run pass 1: largest value reaches index n-1. That slot is now locked.
Run pass 2: second-largest reaches index n-2 (you don't need to compare past n-1).
After pass k: the rightmost k slots are sorted.
Stop when a pass makes zero swaps — the list is sorted.

The early-exit optimization

Track a swapped boolean per pass. If it stays false, the list is already in order and you can exit immediately. This brings the best case (already-sorted input) from O(n²) down to O(n) — exactly one pass with n-1 comparisons and no swaps.

Why it's still O(n²) on average

On random data, each pass moves only one value to its final slot, so you need ~n passes. Each pass does ~n comparisons. That's n × n = O(n²) work. Insertion sort does the same number of comparisons in the worst case but far fewer on average — which is why insertion is what people actually use when they need a tiny in-place sort.

Interactive prototype

Run it. Break it. Tune it.

Sandboxed simulation embedded right in the page. No setup, no install.

simulation › Bubble Sort

About this simulation

Eight bars, one full pass of bubble sort. Press Play to watch the largest value bubble to the end on every round, or use Step / Back to walk through each compare-and-maybe-swap by hand. Try sorted shows the best-case early-exit; Shuffle gives a new random list.

Hands-on

Try these on your own

Open the prototype above, run each experiment, predict the answer, then verify.

try 01

Play through one full sort

Press Play and watch one pass complete. The orange bars are the pair being compared; red bars flash on a swap; the green bar at the right end is the value that's locked in for the pass. Notice that after one pass the largest value is at the end, but the rest are still mostly unsorted.

try 02

Step through with Step / Back

Hit Step to advance one compare-or-swap at a time, Back to rewind. Watch the Comparisons and Swaps counters: every step increments one of them. On a random list of 8, expect ~28 comparisons and ~15 swaps before the list is sorted.

try 03

Try the sorted-data fast path

Press Try sorted to load an already-sorted list. Watch the early-exit kick in: one full pass completes with zero swaps and the algorithm stops on pass 1. That's the best-case O(n) you read about in the trade-offs.

try 04

Shuffle for a new worst case

Press Shuffle repeatedly. Look for inputs where the smallest value sits at the right end — bubble sort has to drag it left one slot per pass, so those inputs take the full n-1 passes. That's the algorithm's worst case made visible.

In practice

When to use it — and what you give up

When it's the right tool

Teaching — the swap-based step is the cleanest introduction to an in-place sort.
Tiny lists where simplicity wins — for n < 10, the constant-factor advantage of cache-friendly code can outweigh the algorithmic disadvantage, but insertion sort already wins here and is just as simple.
Detecting whether a list is already sorted — one pass with the early-exit flag answers that in O(n) and reports zero swaps if so.

When to reach for something else

Anywhere n > ~50 — even insertion sort is meaningfully faster because it doesn't keep swapping past values that are already in place.
Nearly-sorted data — insertion sort handles this in true O(n + d) where d is the number of inversions; bubble's early-exit only helps if zero swaps happen.
Production code — there is no real-world situation where bubble sort is the right answer. Your language's sort() is.

Pros

Trivially simple — four lines, no recursion, no extra memory. You can implement it correctly under exam pressure.
In-place — needs O(1) extra space, just a temp for the swap.
Stable — equal elements never overtake each other, because we only swap on strictly greater-than.
Early-exit detects sorted data in O(n) — one pass, no swaps, done.
Useful pedagogy — the swap-adjacent step is the seed of selection sort, insertion sort, and the partition loop in quick sort.

Cons

O(n²) average and worst case — unusable for n > a few hundred.
Lots of writes — every swap is two assignments. Selection sort makes one swap per pass; bubble can make ~n swaps per pass.
No advantage over insertion sort — same worst case, much worse average case, same simplicity.
Confuses students into using it in interviews — it works, but it signals you didn't pick the right tool.

Reference

Code & further reading

A minimal reference implementation and pointers worth bookmarking.

bubble-sort.ts

// Bubble sort with the early-exit optimization.
// Stable, in-place, O(n) best, O(n²) average and worst.
function bubbleSort<T>(a: T[]): T[] {
  const n = a.length;
  for (let i = 0; i < n - 1; i++) {
    let swapped = false;
    // After pass i, the last i elements are in their final slots.
    for (let j = 0; j < n - 1 - i; j++) {
      if (a[j] > a[j + 1]) {
        [a[j], a[j + 1]] = [a[j + 1], a[j]];
        swapped = true;
      }
    }
    // Zero swaps means the list is already sorted.
    if (!swapped) break;
  }
  return a;
}

// Example
bubbleSort([5, 1, 4, 2, 8]); // → [1, 2, 4, 5, 8]
// On random input of length n, expect ~n²/2 comparisons and ~n²/4 swaps.

References & further reading

5 sources

Knowledge check

Did the prototype land?

Quick questions, answers revealed on submit. No scoring saved.

question 01 / 03

After one full pass of bubble sort on `[5, 1, 4, 2, 8]`, what does the array look like?

question 02 / 03

Why does the early-exit optimization bring the best case down to O(n) but not the worst case?

question 03 / 03

Bubble sort is stable. What does that mean in practice?

0/3 answered