Bubble Sort Visualizer

Bubble sort is the algorithm almost everyone meets first, and the one almost everyone is later told never to use. Both of those things are true, and neither is the interesting part. What makes bubble sort worth an hour of your attention is that it is the smallest complete example of an algorithm you can reason about formally: it has an invariant you can state in one sentence, a proof of correctness you can do in your head, and a cost you can count exactly.

The rule is simple enough to describe without notation. Walk along the array. Whenever two neighbours are in the wrong order, swap them. Reach the end, then start again from the beginning. Keep going until a full walk produces no swaps at all.

What is bubble sort?

Bubble sort is a comparison-based, in-place, stable sorting algorithm that works by repeatedly stepping through a list and swapping adjacent elements that are out of order. The name comes from the way large values appear to rise to the end of the array on each pass, the way a bubble rises through water.

The important structural detail is that bubble sort only ever compares and swaps *neighbours*. It never reaches across the array, never copies into a second buffer, and never needs to know anything about the data beyond whether one element should come before another. That restriction is what makes it so slow — and also what makes it so easy to prove correct.

After the first complete pass, the largest element in the array is guaranteed to be sitting in the final position. Not probably: guaranteed. Once a pass reaches the largest value, every subsequent comparison in that pass finds it larger than its neighbour and carries it one step further right, all the way to the end. After the second pass, the second-largest is in the second-to-last position, and so on. That guarantee is the loop invariant, and it is why the inner loop can shrink by one on every pass.

Why it works

Correctness rests on a single observation: if no adjacent pair is out of order, the whole array is in order. This is not obvious to everyone at first glance, so it is worth spelling out. Suppose every neighbouring pair satisfies a[i] <= a[i+1]. Then by chaining those inequalities — a[0] <= a[1] <= a[2] <= … — every element is less than or equal to every element to its right. Sorted order is exactly that chain.

So bubble sort's termination condition is not a heuristic; it is a complete proof. When the algorithm finishes a pass without swapping anything, it has just verified every adjacent pair, and that verification is equivalent to verifying the entire ordering.

The second half of the argument is that the algorithm must terminate. Every swap strictly reduces the number of *inversions* in the array — pairs of elements that are in the wrong relative order. An array of n elements has at most n(n−1)/2 inversions, each swap removes exactly one, and the algorithm stops when there are none. It cannot loop forever.

Step-by-step walkthrough

Take the array [5, 1, 4, 2, 8] and follow the first pass comparison by comparison.

1. Compare 5 and 1. Out of order, so swap: [1, 5, 4, 2, 8].
2. Compare 5 and 4. Out of order, so swap: [1, 4, 5, 2, 8].
3. Compare 5 and 2. Out of order, so swap: [1, 4, 2, 5, 8].
4. Compare 5 and 8. Already in order, so no swap. The pass ends: [1, 4, 2, 5, 8].

What the remaining passes do

Notice what happened to the 5 in that first pass. It was picked up at the very first comparison that involved it and carried right until it met something larger. That is the characteristic motion of bubble sort: one large value travels a long way per pass, while small values shuffle left only one position at a time. It is the reason bubble sort is so poor on arrays where a small value sits near the end — those elements are sometimes called *turtles*, and each one needs a full pass to move a single step left.

The second pass over [1, 4, 2, 5, 8] compares 1 with 4 (fine), then 4 with 2 (swap, giving [1, 2, 4, 5, 8]), then 4 with 5 (fine). The array is now sorted, but bubble sort does not know that yet. A third pass runs, makes no swaps at all, and *that* is what tells the algorithm to stop.

That final verifying pass is not wasted work — it is the proof. Without it, the algorithm would have to rely on the pass counter alone and always run the full n−1 passes.

How the animation above works

The visualiser does not run bubble sort frame by frame. It runs the real algorithm once, up front, and records every comparison and swap as a small step record. Playback then replays that recording. This is why you can step backwards, jump to the end, and change speed mid-run without the animation ever disagreeing with the algorithm.

Each bar's height is its value. Amber marks the pair currently being compared, coral marks a swap in progress, and mint marks elements that have reached their final position — which, for bubble sort, grows from the right edge inward, one element per pass. The live counters below the bars are incremented by the same step records that drive the colours, so the comparison count you see is the true number of comparisons the algorithm performed, not an estimate.

Time complexity

In the worst case — a reversed array — pass 1 does n−1 comparisons, pass 2 does n−2, and so on. The total is (n−1) + (n−2) + … + 1 = n(n−1)/2, which is O(n²). Every one of those comparisons also triggers a swap on reversed input, so the swap count is O(n²) too. That is the pathological case, and you can watch it happen by choosing the *Reversed* array shape in the controls.

The average case is the same order. For random input roughly half the pairs are inverted, giving about n²/4 comparisons — half the work, but the same growth curve. Constant factors do not change the shape of the wall you hit at scale.

The best case is where bubble sort has a genuine, if narrow, advantage. On an already-sorted array the first pass makes n−1 comparisons, zero swaps, and the early-exit check stops everything. That is O(n) — linear, and better than merge sort's guaranteed O(n log n) on that specific input. It is a real property, and it is also the only situation in which anyone should reach for this algorithm.

Space complexity

Bubble sort is O(1) auxiliary space. It sorts inside the original array and needs only a handful of loop counters and one temporary variable for the swap, regardless of how large the input is. This is what *in-place* means, and it is bubble sort's one unambiguous strength over merge sort, which needs an O(n) scratch buffer.

It is also stable: because it only swaps strictly out-of-order neighbours (a[i] > a[i+1], never >=), two equal elements are never exchanged, so their original relative order survives. Stability matters more than beginners expect — it is what lets you sort a table by one column and then another without the first sort being scrambled.

Complexity at a glance

The numbers below are what the counters in the visualiser converge on. Raise the array size and watch the comparison count grow at the rate this table predicts.

Pseudo code

Language-agnostic, and close enough to the implementations below that you can read them side by side.

Bubble Sort in five languages

Working reference implementations — copy or download any of them. They are written to be read, so the comments explain the decisions rather than restating the code.

/**
 * Bubble sort with the early-exit optimisation.
 * Sorts in place and returns the same array for convenience.
 */
function bubbleSort(arr) {
  let n = arr.length;
  let swapped;

  do {
    swapped = false;
    for (let i = 0; i < n - 1; i++) {
      if (arr[i] > arr[i + 1]) {
        [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
        swapped = true;
      }
    }
    // After a pass the largest unsorted value is at the end, so the
    // next pass can stop one position earlier.
    n--;
  } while (swapped);

  return arr;
}

console.log(bubbleSort([5, 1, 4, 2, 8])); // [1, 2, 4, 5, 8]

Advantages and disadvantages

Real-world applications

• Teaching loop invariants, correctness proofs and complexity analysis — its real and lasting use.
• Detecting whether a nearly-static dataset has drifted out of order, where the single-pass early exit is the entire point and sorting is the rare path.
• Tiny fixed-size arrays in memory-constrained embedded firmware, where code size matters more than speed and the input is known to be a handful of elements.
• Educational visualisations and interview warm-ups, where the goal is to demonstrate understanding of a technique rather than to sort quickly.
• Bubble sort's cousin, cocktail shaker sort, appears occasionally in graphics code for keeping a nearly-sorted list of primitives ordered between frames.

Interview questions

The questions that actually get asked about Bubble Sort, with the answers an interviewer is listening for.

1. Q1. Why is bubble sort O(n) in the best case but O(n²) in the average case?

   The best case relies on the early-exit flag. On sorted input the first pass performs n−1 comparisons, makes zero swaps, and the flag stops the algorithm — one linear pass. On random input roughly half the adjacent pairs are inverted, so passes keep swapping and the algorithm runs the full sequence of shrinking passes, giving about n²/4 comparisons.

2. Q2. Is bubble sort stable, and what makes it so?

   Yes. The comparison is strict (a[i] > a[i+1]), so two equal elements are never swapped. Change it to >= and the algorithm still sorts correctly but loses stability — equal elements would be exchanged for no reason, scrambling their original order.

3. Q3. How would you optimise bubble sort further than the early-exit flag?

   Track the index of the last swap in each pass and make that the boundary for the next pass, rather than just decrementing by one — everything beyond the last swap is already sorted. The other standard variant is cocktail shaker sort, which alternates direction each pass so that small values near the end migrate left quickly instead of one step per pass.

4. Q4. Compare bubble sort with insertion sort. When would you pick either?

   They share the same O(n²) worst case and O(n) best case, but insertion sort does substantially fewer writes and moves elements with shifts rather than repeated swaps, so it is faster on essentially every real input. The honest answer in an interview is that you would pick insertion sort, and that bubble sort's value is pedagogical.

5. Q5. What is an inversion, and how does it relate to bubble sort's running time?

   An inversion is a pair (i, j) where i < j but a[i] > a[j]. Each adjacent swap removes exactly one inversion, so bubble sort's swap count equals the number of inversions in the input. That makes its running time proportional to how far the array is from sorted, which is the precise statement of what people mean when they call it adaptive.

Common mistakes

• Omitting the early-exit flag, which silently destroys the O(n) best case and makes the algorithm always run the full n−1 passes.
• Forgetting to shrink the inner loop bound after each pass, so the algorithm keeps re-comparing elements that are already in their final positions.
• Writing the inner loop as i <= n - 1, which reads arr[i + 1] one element past the end of the array — the classic off-by-one that produces an out-of-bounds error or, worse, silently reads garbage in C.
• Using >= instead of > in the comparison, which makes the algorithm unstable while doing strictly more work.
• Assuming the array is sorted after a fixed number of passes without checking — the terminating pass that makes no swaps is what proves the result.

Optimisation tips

• Record the position of the final swap in each pass and use it as the next pass's upper bound; on many inputs this eliminates several passes at once.
• Switch direction on alternate passes (cocktail shaker sort) so both large values and small ones move quickly, which fixes the turtle problem.
• If the data is nearly sorted and you only need to *know* whether it is sorted, run a single comparison pass and skip the sort entirely.
• For any array larger than roughly twenty elements, use insertion sort instead — same simplicity, same asymptotics, meaningfully fewer writes.
• In production, call your language's built-in sort. It is almost certainly an introsort or Timsort hybrid that has been tuned harder than anything you will write by hand.

Summary

Bubble sort repeatedly compares adjacent elements and swaps the ones that are out of order, one pass at a time, until a full pass makes no swaps. Its cost is O(n²) in the average and worst cases, O(n) on already-sorted input with the early-exit flag, and O(1) in extra memory. It is stable and in place.

As a production algorithm it has no serious use. As a teaching object it is nearly perfect: the invariant is one sentence, the correctness argument fits in a paragraph, and the counters in the visualiser above let you watch the quadratic curve appear as you raise the array size from 10 to 200. Understand it properly, then reach for insertion sort — and in real code, for the sort your standard library ships.

Frequently asked questions

Related algorithms

• Insertion Sort

  Grow a sorted prefix by sliding each new value back to where it belongs.

  O(n²)Beginner

• Selection Sort

  Scan for the smallest remaining value and swap it into place — one swap per pass.

  O(n²)Beginner

• Quick Sort

  Partition around a pivot so everything smaller lands left and larger lands right.

  O(n log n)Intermediate