Bubble sort

Walk the array comparing neighbours, and swap any pair that is out of order. Each pass carries the largest remaining value to the end, like a bubble rising. Stop when a pass swaps nothing.

best O(n)worst O(n²)in placestable

53819274

Press play or step forward to start.

step 0 / 46

1function bubbleSort(a) {2  for (let end = a.length - 1; end > 0; end--) {3    let swapped = false;4    for (let j = 0; j < end; j++) {5      if (a[j + 1] < a[j]) {6        swap(a, j, j + 1);7        swapped = true;8      }9    }10    if (!swapped) return;11  }12}

Keys: Space play or pause, ← → step. The URL always points at the frame you are on.

What it costs

Case	Time	When
best	n	already sorted: one pass with no swaps, then stop
average	n²	random input
worst	n²	reversed input: every pair swaps
space	1	sorts in place

Where it breaks

Almost any real input. It makes as many compares as insertion sort and far more writes. Pick Reversed above: 28 compares and 56 writes for 8 items. It is worth learning for the idea, not for use.
Small values stuck at the end. A large value bubbles right in one pass, but a small one moves left only one step per pass. Try 2, 3, 4, 5, 6, 7, 8, 1: the 1 needs seven passes.
Without the early stop. Drop the swapped check and sorted input costs the full n(n−1)/2 compares too. Pick Sorted to see it finish in one pass instead.