How bubble sort works
- Compare the first two values. If the left one is greater, swap them.
- Move one position to the right and do the same with the next pair, up to the end of the unsorted part.
- After the pass, the largest value of that part sits at its right end, in its final place.
- Repeat on a part that is one value shorter. After n - 1 passes there is nothing left to sort.
What the colours mean
Yellow bars are the pair being compared. Pink bars have just been swapped, and green bars are in their final place. Bars outside the current pass are faded. The j under the bars is the same j as in the code.
Bubble Sort time and space complexity
| Best case | Average case | Worst case | Extra space | Stable |
|---|---|---|---|---|
| O(n²) | O(n²) | O(n²) | O(1) | Yes |
This version makes n(n - 1)/2 comparisons whatever the order of the input: 45 for 10 values. Choose Already sorted and the comparison counter still ends at 45, while the write counter stays at 0. The article adds a flag that stops after a pass with no swaps, and that brings the best case down to O(n).
Each swap is two array writes. A reversed array of 10 different values swaps on every comparison, so it ends at 90 writes.
The C# code
The listing beside the bars is the SortArray() method from Bubble Sort In C#. The article explains the code and measures it with BenchmarkDotNet.
FAQ
Is bubble sort stable?
Yes. It swaps two neighbours only when the left one is strictly greater, so equal values never pass each other.
Why is bubble sort slow?
It only swaps neighbours, so a value moves one position at a time. A value that starts far from its place needs many swaps, and the number of comparisons grows with the square of the array size.
How many passes does bubble sort need?
At most n - 1 for n values. Each pass puts one more value in its final place at the right end, and the last value left over is already in place.