Bubble Sort

Intuition

Bubble sort treats the array as a row of bars and "bubbles" the largest value to the right end on every pass. Compare two neighbors, swap them if they're out of order, then slide one slot to the right. After the first pass the biggest element is parked at the end. After the second pass the second-biggest joins it. After at most n − 1 passes the whole array is sorted.

The name comes from the way the largest unsorted value seems to rise to the top of the array, the way a bubble rises through water.

How It Works

Bubble sort runs two nested loops:

Outer loop counts the pass index i from 0 to n − 2. Each pass parks one more value at its final position, growing the sorted suffix on the right.
Inner loop sweeps j from 0 to n − 2 − i. Each iteration looks at arr[j] and arr[j + 1], swapping when the left one is larger.

The key invariant: after pass i, the last i + 1 cells of the array already hold the i + 1 largest values in sorted order. That's why each pass can stop one position earlier on the right.

Step By Step

For the default input [38, 12, 56, 7, 41, 23, 19]:

Compare 38, 12 → swap → [12, 38, 56, 7, 41, 23, 19]
Compare 38, 56 → no swap.
Compare 56, 7 → swap → [12, 38, 7, 56, 41, 23, 19]
Compare 56, 41 → swap → [12, 38, 7, 41, 56, 23, 19]
Compare 56, 23 → swap → [12, 38, 7, 41, 23, 56, 19]
Compare 56, 19 → swap → [12, 38, 7, 41, 23, 19, 56]
End of pass 1. 56 is parked at the right edge.
Pass 2 starts at j = 0. Compare 12, 38 → no swap.
Compare 38, 7 → swap → [12, 7, 38, 41, 23, 19, 56]
Compare 38, 41 → no swap.
Compare 41, 23 → swap → [12, 7, 38, 23, 41, 19, 56]
Compare 41, 19 → swap → [12, 7, 38, 23, 19, 41, 56]
End of pass 2. 41 parks next to 56.
Passes 3-6 continue the same pattern, settling 38, 23, 19, and 12 in turn until the array is fully sorted to [7, 12, 19, 23, 38, 41, 56].

In the visualization, watch the pointer j walk across the bars. When a swap fires, the two bars slide past each other. A green-tinted bar means "settled at its final position".

Complexity

The version animated here is the textbook two-loop bubble sort with no early termination — it always runs the full n − 1 outer passes, regardless of whether the array became sorted along the way.

Case	Time
Best	O(n²)
Average	O(n²)
Worst (reverse sorted)	O(n²)

Space: O(1) — sorting happens in place, no auxiliary array.

Optimization (not animated): add a swapped flag that resets to False at the top of each outer pass and gets set whenever the inner loop performs a swap. If swapped is still False at the end of a pass, the array is already sorted and the algorithm can return early. That variant drops the best case (already-sorted input) to O(n) — a single linear scan. The lesson keeps the unoptimized form because the fixed n − 1 outer passes make the visual rhythm easier to follow.

Bubble sort is rarely used in practice. Production languages ship faster sorts (quicksort, mergesort, Timsort). The reason to learn it: it's the simplest illustration of adjacent-pair comparisons, and the same mental model carries directly into insertion sort and shell sort.

Edge Cases

Empty or one-element array — zero passes, returns immediately.
Already sorted input — the unoptimized form still runs every outer pass; you'd see the inner loop sweep across without firing a single swap. The early-exit variant above is what cuts this to O(n).
All equal values — bubble sort is stable: equal elements are never swapped past each other, so their original order is preserved.

Common Mistakes

Off-by-one on the inner loop bound. It should run to n − 2 − i, not n − 1. The "sorted suffix" grows by one each pass; comparing into it wastes work and can mis-color settled elements.
Forgetting the temp variable when swapping in languages without tuple assignment. Writing arr[j] = arr[j + 1] first and then arr[j + 1] = arr[j] loses the original arr[j] — it's already been overwritten.
Treating "out of order" as >= instead of >. Using >= swaps equal elements unnecessarily and breaks stability.