Sorting Algorithms
quadratic · in place · stable

Watch <bubble sort> run.

Walk the array, swap neighbours that are out of order, repeat until a pass changes nothing. Every comparison, every swap, and the line that caused it — the point is the why, not the animation.

What it costs

Best case
O(n)An already-sorted array. One pass makes no swaps, the swapped flag stays false and the loop stops. Without that flag it would still be O(n²).
Average
O(n²)Roughly n²/4 swaps — every value has to walk to its place one position at a time.
Worst case
O(n²)A reversed array. Every comparison swaps: n(n−1)/2 of them.
Extra memory
O(1)It sorts in place — one temporary variable, whatever the size of the input.
Stable
YesEqual values never swap past one another, because the test is strictly greater-than. Change it to >= and you lose that.
Used in practice
NoInsertion sort beats it on the same inputs and is barely harder to write. Bubble sort survives because the movement is easy to see — which is the whole point of this page.