Bubble Sort

What is bubble sort?

Bubble sort puts a list in order by looking at two neighbors at a time. If the left one is bigger, it swaps them. Then it moves one step right and does it again.

After one full pass, the biggest value has been pushed all the way to the end, the way a bubble rises to the top of a glass. That’s where the name comes from. The next pass does the same thing for the second biggest value, and so on, until every value is in place.

It is usually the first sorting algorithm people learn. It isn’t fast, but every step is easy to see, which makes it a great way to learn how sorting works at all.

How it works, step by step

Press play on the demo above and follow along. The blue bars are being compared. The orange bars are being swapped. Green bars are done.

1. Start at the left. Compare a[0] and a[1].
2. If the left value is bigger, swap them. If not, leave them.
3. Move one step right and compare a[1] and a[2]. Keep going to the end of the unsorted part.
4. The biggest value is now at the end. Mark it as sorted. The next pass can stop one step earlier.
5. Repeat. If a whole pass makes no swaps, the list is already sorted, so stop early.

In the code, the outer loop counts passes (p) and the inner loop walks across the unsorted part (i). The swapped flag is the early exit from step 5. Watch the highlight in the code panel: every compare lights up the if line, and every swap lights up the line under it.

Time and space complexity

Say the list has n values. The first pass makes n − 1 comparisons, the next makes n − 2, and so on down to 1. Add those up and you get about n²/2 comparisons. That grows with the square of n, so bubble sort is O(n²) on average and in the worst case.

What does that mean in practice? Sorting 10 values takes about 45 comparisons. Sorting 1,000 values takes about 500,000. Doubling the list makes the work four times bigger.

The worst case is a list in reverse order: every comparison finds a pair out of order, so every comparison is also a swap. Try the “reversed” preset above and watch the swap counter climb.

The best case is a list that is already sorted. The first pass finds nothing to swap, the swapped flag stays false, and the loop stops after n − 1 comparisons. That’s O(n). Without the early exit, bubble sort would do all the passes anyway and stay O(n²) even on sorted input.

Bubble sort needs O(1) extra space. It sorts the list in place and only keeps a few counters.

Common mistakes

• Going one step too far. The inner loop compares a[i] with a[i + 1], so it must stop at n − 1 − p, or it reads past the end of the list.
• Forgetting to shrink the inner loop. The last p values are already sorted after p passes. Checking them again still gives the right answer, but wastes time.
• Leaving out the early exit. It is one flag and one break, and it turns sorted input from O(n²) into O(n).
• Swapping on >= instead of >. Equal values would trade places for no reason, and the sort would stop being stable (equal values would no longer keep their original order).

When to use it

Almost never in real code. Your language’s built-in sort (Python’s sorted, JavaScript’s Array.prototype.sort, Go’s slices.Sort) is much faster and already tested.

Bubble sort is still worth knowing. It is the easiest way to see what “compare and swap” means, it shows why O(n²) is slow, and interviewers like to ask how to improve it. Two common answers are cocktail shaker sort, which sweeps in both directions, and comb sort, which compares values far apart first.

It can also be fine for tiny lists that are almost sorted, where one or two passes finish the job.

Questions

Is bubble sort stable?

Yes. It only swaps when the left value is strictly bigger, so equal values never pass each other.

Why is it called bubble sort?

Big values rise to the end of the list one swap at a time, like bubbles rising in water.

Is bubble sort faster than insertion sort?

Both are O(n²), but insertion sort usually does fewer swaps and runs faster in practice, especially on lists that are nearly sorted.