Bubble Sort

Bubble sort repeatedly compares neighbouring values and swaps them when they are in the wrong order, so the largest value "bubbles" to the end on every pass.

Start

5
3
8
2
1
  • Comparing
  • Swapping
  • In final place

5 values. Bubble sort walks the list comparing neighbours, swapping any pair in the wrong order.

Step 1 / 28
Pass
0
Comparisons
0
Swaps
0
for i from 0 to n − 1:
swapped = false
for j from 0 to n − i − 2:
if a[j] > a[j + 1]:
swap(a[j], a[j + 1]); swapped = true
if not swapped: stop — it is sorted

Step by step

The example above, written out — the same steps the animation plays.

  1. 1Start. 5 values. Bubble sort walks the list comparing neighbours, swapping any pair in the wrong order.
  2. 2Pass 1. Pass 1: the largest unsorted value will bubble to the end.
  3. 3Compare 5 and 3. 5 > 3 — out of order.
  4. 4Swap. Swap: 3 moves left, 5 moves right.
  5. 5Compare 5 and 8. 5 ≤ 8 — already in order.
  6. 6Compare 8 and 2. 8 > 2 — out of order.
  7. 7Swap. Swap: 2 moves left, 8 moves right.
  8. 8Compare 8 and 1. 8 > 1 — out of order.
  9. 9Swap. Swap: 1 moves left, 8 moves right.
  10. 108 is in place. End of pass 1: 8 has reached its final position.
  11. 11Pass 2. Pass 2: the largest unsorted value will bubble to the end.
  12. 12Compare 3 and 5. 3 ≤ 5 — already in order.
  13. 13Compare 5 and 2. 5 > 2 — out of order.
  14. 14Swap. Swap: 2 moves left, 5 moves right.

…and 14 more steps — press Play above to watch them all.

What's happening?

  1. Each pass walks the unsorted part from left to right, comparing pairs of neighbours.
  2. A pair in the wrong order swaps; after one pass the largest remaining value is at the end and never moves again.
  3. If a whole pass makes no swaps, the list is already sorted and the algorithm stops early.

Complexity

Time
O(n²) worst and average · O(n) best (already sorted)
Space
O(1) — it sorts in place

Where you'll meet it

Almost never used for real data — it exists to teach comparing, swapping and loop invariants. Libraries use merge sort, quicksort or Timsort instead.

Common mistake

Forgetting that each pass can stop one position earlier: after pass k, the last k values are already in place.

FAQ

Why is bubble sort O(n²)?

In the worst case each of about n passes compares about n pairs, so the work grows with n × n.

Is bubble sort stable?

Yes. Equal values are never swapped, so their original order is kept.

When does bubble sort finish in one pass?

When the list is already sorted: the first pass makes no swaps and the algorithm stops.