Bubble sort makes repeated passes over the array, comparing every adjacent pair and swapping them if they're out of order. Nothing gets pulled out and carried like insertion sort's key, and nothing gets scanned for ahead of time like selection sort's minimum — each pass only ever looks at two neighbors at a time. The name comes from what that does to large values: on every pass, the largest element still unsorted "bubbles" all the way to the end, one swap at a time, because it's bigger than everything it gets compared against.
Enter a comma-separated list of numbers, then step through the sort. The bordered pair of bars is the pair currently being compared; a flash to the accent color marks a swap. Bars in the shaded region on the right are finalized — bubble sort's sorted region grows from the end, not the start.
The invariant: after pass i (0-indexed), the last i + 1 elements
of the array hold the i + 1 largest values, in final sorted position. Each pass
walks left to right comparing arr[j] against arr[j + 1], swapping when
the left one is bigger. Every time a swap happens, whichever value is larger moves one slot to
the right; do that for every adjacent pair across the whole unsorted prefix and the single
largest value among them is guaranteed to have moved right on every comparison it was part of,
landing at the very end of the pass. The next pass repeats the same walk over one fewer element,
since the last one is now settled.
function bubbleSort(arr) {
const n = arr.length;
for (let i = 0; i < n - 1; i++) {
let swapped = false;
for (let j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
swapped = true;
}
}
if (!swapped) break; // early exit: a clean pass means the array is sorted
}
return arr;
}Without the swapped flag, there's no adaptive best case at all.
Drop the if (!swapped) break line and bubble sort runs every one of its n - 1
passes regardless of input, even on an array that's already sorted — every pass still has to
scan and compare, it just never swaps. Checked directly against the shipped generator above,
toggling the checkbox: on an already-sorted array of 7 elements, the unoptimized version still
runs 6 full passes and 21 comparisons before declaring victory, while the early-exit version
detects a swap-free first pass and stops after 1 pass and 6 comparisons — the exact O(n)
best case insertion sort gets for free from its own early-terminating inner loop. On the page's
own default array (which needs real work), both versions land on the same 9 swaps, but early
exit still saves 2 full passes and 3 comparisons (18 vs. 21) by recognizing the array is done one
pass before the unoptimized version would bother checking again.
Shrinking the inner bound matters even with early exit. The inner loop runs to
n - 1 - i, not a fixed n - 1, because everything from index
n - i onward is already known-sorted from prior passes — comparing into it again
can't find anything out of order, it can only waste time. Confirmed by re-running the same
generator logic with the inner bound fixed at n - 1 on every pass: same final
array, same correctness, but 36 comparisons instead of 21 on the page's own default 7-element
array — a pitfall that costs performance silently, never correctness, so nothing about a normal
test run would ever catch it.
Stability, and why it's the opposite story from selection sort. The swap
condition is arr[j] > arr[j + 1], strictly greater — equal elements never swap
past each other, and since every swap only ever exchanges adjacent slots, two equal
elements can never leapfrog anything sitting between them the way selection sort's long-range
swap can. Bubble sort is stable. Running the tagged-pair check from selection sort's own Pitfalls section —
[3♥, 5, 3♦, 1] — through the reference implementation above confirms it:
the result is [1, 3♥, 3♦, 5], with 3♥ still ahead of 3♦, unlike selection sort's
[1, 5, 3♦, 3♥] on the same input.
Time: O(n²) worst and average case. Best case is
O(n), but only with the early-exit optimization — an already-sorted array
still costs the full O(n²) without it, unlike insertion sort's inner loop, which is
adaptive by construction with no extra flag needed. Space: O(1)
extra, sorts in place. Swaps: up to n(n-1)/2 in the worst case
(reverse-sorted input swaps on every single comparison) — no write-count advantage the way
selection sort has one.
Selection sort and bubble sort make the same asymptotic worst-case bet, but they're a study in
contrasts: selection sort's comparison count never changes no matter the input, while its swap
count is bounded by how many elements are actually out of place. Bubble sort is the reverse —
its swap count depends entirely on how out-of-order the input is, while its comparison count is
only bounded once the early-exit optimization is in place. Neither is what you'd reach for at
scale; both exist here mainly to build intuition before merge sort and quicksort's O(n log n) guarantees. See Choosing a Comparison Sort for how all ten
comparison sorts on this site stack up against each other.