Bubble sort walks the array comparing each pair of neighbours, swapping them when they are the wrong way round. After a full pass the largest value it has seen has been carried all the way to the end, so the next pass can stop one position earlier. Repeat until a pass makes no swaps at all.
Press play, or step through it one comparison at a time. Orange is the pair being compared, yellow is a swap in progress, and green is locked in for good.
Ready. 14 values, unsorted.
0 comparisons · 0 swaps
Ready. 14 values, unsorted.
- Comparing
- Swapping
- Sorted
Code
- def bubble_sort(a):
- n = len(a)
- for i in range(n - 1):
- swapped = False
- for j in range(n - 1 - i):
- if a[j] > a[j + 1]:
- a[j], a[j + 1] = a[j + 1], a[j]
- swapped = True
- if not swapped:
- break
- return a
Try Worst case to watch every single comparison turn into a swap, then Best case to see the early exit stop the whole thing after one pass. That gap between
the two is the difference between O(n²) and O(n).
Time and space complexity
| Case | Complexity | Why |
|---|---|---|
| Best | O(n) | Already sorted. One pass makes no swaps and the early exit fires. |
| Average | O(n²) | Random order. Roughly n²/4 swaps. |
| Worst | O(n²) | Reverse sorted. Every comparison swaps. |
| Space | O(1) | Sorts in place. Only a temporary for the swap. |
| Stable | Yes | Equal values never swap, so their order is preserved. |
That O(n) best case is not free — it depends entirely on the swapped flag in
the code below. Take the flag out and you always do all n passes, whatever the
input looks like.
Step by step
- Start at the first pair, indices
0and1. - Compare the two values.
- If the left one is larger, swap them.
- Move one position right and repeat to the end of the array. That is one pass.
- The largest value has now bubbled to the end, so the next pass can stop one position earlier.
- Stop as soon as a full pass makes no swaps. Nothing is left out of order.
Worked example
Sorting [5, 2, 4, 1]:
| Pass | Result | What happened |
|---|---|---|
| 1 | [2, 4, 1, 5] | Swap 5 and 2, swap 5 and 4, swap 5 and 1. 5 reaches the end. |
| 2 | [2, 1, 4, 5] | 2, 4 are fine; swap 4 and 1. 4 is now placed. |
| 3 | [1, 2, 4, 5] | Swap 2 and 1. The rest are already in order. |
| 4 | [1, 2, 4, 5] | A full pass with no swaps, so it stops here. |
Four values took three passes of real work and one to confirm. Without the early-exit check it would have done the fourth pass regardless.
When to use it
| Reach for it when | Avoid it when |
|---|---|
| You are learning or teaching how comparison sorts work | The input is large — O(n²) gets away from you fast |
| The input is tiny, or nearly sorted already | You want the fastest general-purpose sort — use quicksort or merge sort |
| You need a stable in-place sort in almost no code | Writes are expensive; selection sort does far fewer swaps |
| You want a one-pass check that a short list is sorted | The data is in random order and speed matters at all |
The code
Every version below includes the early-exit flag, so the complexity table above holds whichever one you read.
def bubble_sort(a):
n = len(a)
for i in range(n - 1):
swapped = False
for j in range(n - 1 - i):
if a[j] > a[j + 1]:
a[j], a[j + 1] = a[j + 1], a[j]
swapped = True
if not swapped:
break
return a
nums = [5, 1, 4, 2, 8]
bubble_sort(nums)
print(nums)
Common questions
What is the time complexity of bubble sort?
O(n²) on average and in the worst case: each of the n passes does up to n comparisons. With the early-exit check the best case is O(n), because one clean pass over an already sorted array finds nothing to swap and stops.
Is bubble sort stable?
Yes. It only swaps when the left value is strictly greater than the right one, so two equal values never trade places and their original relative order survives.
Why is it called bubble sort?
Because of what the animation shows. On every pass the largest remaining value keeps swapping rightwards until it reaches the end, so large values appear to bubble up to the surface of the array.
How is bubble sort different from insertion sort?
Both are O(n²) and both are stable, but they move data differently. Bubble sort repeatedly swaps neighbours across the whole array. Insertion sort grows a sorted prefix and shifts each new value back into place, which means far fewer writes and makes it noticeably faster on nearly sorted data.
Should I use bubble sort in real code?
Almost never. Every mainstream language ships a sort that is O(n log n) and heavily optimised, so use that. Bubble sort earns its place as a teaching tool, and occasionally as a two-line check that a very short list is already in order.
Does the early-exit check improve the worst case?
No. It only helps when a pass finds nothing to swap. On reverse-sorted input every pass swaps something, so the flag is always true and you pay the full O(n²).