Step through one of the most intuitive sorting algorithms where larger elements "bubble up" to the end.
Overview
Quick Context: What is Bubble Sort?
Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted. The algorithm gets its name because smaller or larger elements "bubble" to their proper place.
Parameters
12
Visualization
Step: 0
Click Randomize or Step to begin sorting.
Algorithm Insight
Bubble Sort repeatedly swaps adjacent elements if they are in the wrong order.
1.Compare two adjacent elements.
2.If $Left > Right$, swap them.
3.Move to the next pair.
4.After one pass, the largest element is at the end.
Complexity
Average CaseO(N²)
Space ComplexityO(1)
Deconstructing Bubble Sort
How this simple, intuitive sorting algorithm works. Use this guide after interacting with the visualizer.
The Core Idea: Compare and Swap
The entire algorithm is built on one fundamental operation: comparing two adjacent items and swapping them if the first is larger than the second. This process is repeated from the beginning of the array to the end. After the first full pass, the largest element in the array will have "bubbled up" to the very last position. The next pass does the same for the second-largest element, and so on.
Swapping neighbours until nothing moves
Bubble sort compares each adjacent pair and swaps them if they are out of order. One pass moves the largest remaining element to the end — it "bubbles up". Repeat until a pass makes no swaps.
Sorting [5, 1, 4, 2]:
Pass
Comparisons
Result
1
5>1 swap, 5>4 swap, 5>2 swap
[1, 4, 2, 5]
2
1<4 no, 4>2 swap, 4<5 no
[1, 2, 4, 5]
3
No swaps — stop
[1, 2, 4, 5]
def bubble_sort(arr):
n = len(arr)
for i in range(n):
swapped = False
for j in range(n - 1 - i): # -i: the tail is already sorted
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
if not swapped:
break # already sorted; stop early
return arr
Two details make this the "optimised" version. The - i skips the sorted tail, halving the comparisons. The swapped flag stops immediately on sorted input, giving O(n) in the best case.
Why it is slow
Case
Complexity
When
Best
O(n)
Already sorted — one pass, no swaps
Average
O(n²)
Random order
Worst
O(n²)
Reverse sorted
Space
O(1)
In place
The problem is that each swap moves an element by exactly one position. An element at the wrong end of the array needs n swaps to reach its place, and with n such elements the total work is quadratic.
Compare with insertion sort, which does the same number of comparisons in the worst case and typically fewer swaps, or with shell sort, which is bubble-like but compares elements far apart first so they travel quickly.
The practical numbers: at n = 10,000 bubble sort does about 50 million comparisons; Timsort does about 130,000. On a modern machine that is roughly a second against a few milliseconds.
Why it is taught anyway
Bubble sort is genuinely never the right choice in production — insertion sort dominates it for small arrays, and library sorts dominate everything for large ones. Its value is didactic, and there are three real reasons it appears first:
It is the simplest correct sort to write and to verify. The invariant — after pass i, the last i elements are in final position — is easy to state and check.
It introduces stability. Because it only swaps strictly out-of-order neighbours, equal elements never cross. Changing > to >= breaks that, which is a memorable demonstration of how a single character decides stability.
It makes the cost of moving elements one step at a time visible, which motivates every faster algorithm: merge sort's halving, quick sort's partitioning, shell sort's gaps.
Algorithm
Best
Average
Worst
Stable
In place
Bubble
O(n)
O(n²)
O(n²)
Yes
Yes
Insertion
O(n)
O(n²)
O(n²)
Yes
Yes
Selection
O(n²)
O(n²)
O(n²)
No
Yes
Merge
O(n log n)
O(n log n)
O(n log n)
Yes
No
Quick
O(n log n)
O(n log n)
O(n²)
No
Yes
Timsort
O(n)
O(n log n)
O(n log n)
Yes
No
Exploration guide
One Full Pass: Click "Randomize Array", then click "Next Step" repeatedly. Watch the two active bars (the ones being compared). Notice how the larger value always moves to the right after a swap. After you've gone through the whole array once, observe that the largest bar is now at the far right, in its final sorted position.
The Sorted Section: As you complete each full pass, you'll see the sorted elements accumulate at the end of the array. The algorithm is smart enough to know it doesn't need to check this sorted section again, making each subsequent pass slightly shorter.
Best Case Scenario: Manually create a nearly sorted array (or hope "Randomize" gives you one!). Start the sort. An optimized Bubble Sort can detect if no swaps were made during a full pass. If so, it knows the array is already sorted and can stop early.
Worst Case Scenario: A reverse-sorted array is the worst case. Every single comparison will result in a swap. Run this to see the maximum number of steps the algorithm can take.
Pseudocode
# Basic bubble sort, with the early exit
for i in range(n - 1):
swapped = False
for j in range(n - 1 - i): # the last i items are already final
if a[j] > a[j + 1]:
a[j], a[j + 1] = a[j + 1], a[j]
swapped = True
if not swapped: # a clean pass means it is sorted
break
The outer loop i tracks how many elements are already sorted at the end. The inner loop j performs the adjacent comparisons.
Performance & When to Use It
Bubble Sort has a time complexity of O(n²) in the average and worst cases, which is very slow for large datasets. Its main advantages are its simplicity and the fact that it requires O(1) extra space.
Because of its poor performance, Bubble Sort is rarely used in production systems. It serves primarily as an educational tool to introduce sorting concepts and the idea of algorithmic analysis.
Bubble against insertion sort
The two are the same complexity and insertion sort is strictly better in practice, which is worth understanding rather than just asserting.
Both are O(n²) and both are O(n) on sorted input. The difference is the number of writes: bubble sort swaps repeatedly to move one element into place, while insertion sort shifts elements and places the target once.
For nearly-sorted data insertion sort is dramatically better, and that is why real sorting implementations use insertion sort, not bubble sort, for small subarrays. Timsort switches to it below 32–64 elements; introsort does the same.
So the honest summary: bubble sort's niche is teaching, and insertion sort occupies the niche bubble sort appears to be for.
Variants
Cocktail shaker sort alternates direction each pass — left to right, then right to left. It fixes "turtles", small elements near the end that bubble sort moves only one position per pass. Still O(n²), and measurably faster on some inputs.
Comb sort compares elements a gap apart, shrinking the gap each pass until it reaches 1. That lets elements travel far in one move, and it approaches O(n log n) in practice. It is essentially the same insight as shell sort applied to bubble sort.
Odd-even sort alternates comparing odd-indexed and even-indexed pairs. It exists because those comparisons are independent, so it parallelises — the one context where a bubble-family algorithm has a genuine advantage.
That parallel variant is the honest exception to "never use bubble sort": on hardware where comparisons are free and communication is expensive, its local, regular access pattern matters more than its complexity.
Common mistakes
Omitting the early-exit flag, which loses the O(n) best case for no benefit.
Omitting - i, which re-compares the already-sorted tail every pass.
Using >= instead of >, which swaps equal elements and destroys stability.
Off-by-one in the inner range, reading arr[j+1] past the end.
Using it on real data.sorted() is Timsort in C and is faster by orders of magnitude.
Counting what it actually does
Bubble sort is worth running rather than reading, because the counts explain both why it is slow and why the early-exit version is genuinely different from the naive one. Instrument it and the O(n squared) stops being an assertion.
example_01.pyPython
def bubble(a, early_exit=True):
a = a[:]
comps = swaps = passes = 0
n = len(a)
for i in range(n - 1):
passes += 1
moved = False
for j in range(n - 1 - i):
comps += 1
if a[j] > a[j + 1]:
a[j], a[j + 1] = a[j + 1], a[j]
swaps += 1
moved = True
if early_exit and not moved:
break # a clean pass means it is sorted
return a, comps, swaps, passes
cases = {
"already sorted": list(range(10)),
"reversed": list(range(10))[::-1],
"one out of place": [0, 1, 2, 3, 4, 5, 6, 7, 9, 8],
"random-ish": [5, 1, 9, 3, 7, 0, 8, 2, 6, 4],
}
print("%-18s %6s %6s %7s %s" % ("input", "comps", "swaps", "passes", "early exit?"))
for name, data in cases.items():
for flag in (True, False):
_, c, s, p = bubble(data, flag)
print("%-18s %6d %6d %7d %s" % (name if flag else "", c, s, p, flag))
# Read the two rows for "already sorted": with the early exit it makes one
# pass and 9 comparisons; without it, 45 comparisons and 9 passes for a
# list that was finished before it started. That single boolean is the
# whole difference between O(n) and O(n^2) on sorted input.
#
# Then read "reversed": 45 comparisons and 45 swaps either way. Every
# comparison finds a pair out of order, so the early exit never fires.
# That is the worst case, and it is exactly n(n-1)/2.
n = 10
print()
print("n(n-1)/2 for n=%d is %d" % (n, n * (n - 1) // 2))
# One more property, and it is the reason bubble sort is not merely a bad
# quick sort: it is STABLE. Equal elements keep their original order,
# because the swap condition is > rather than >=.
pairs = [("b", 2), ("a", 1), ("c", 2), ("d", 1)]
def bubble_pairs(items, strict):
items = items[:]
for i in range(len(items) - 1):
for j in range(len(items) - 1 - i):
worse = items[j][1] > items[j + 1][1] if strict else \
items[j][1] >= items[j + 1][1]
if worse:
items[j], items[j + 1] = items[j + 1], items[j]
return items
print("input ", pairs)
print("with > (stable)", bubble_pairs(pairs, True))
print("with >= (broken)", bubble_pairs(pairs, False))
# Sorting by the number only: with > the two 1s stay in their original
# order (a before d) and so do the 2s (b before c). With >= they are
# swapped whenever they meet, and the original order is lost. Stability
# is not a happy accident of the algorithm -- it is that one character.
Output
Questions people ask
Is bubble sort ever the right choice? Practically no. Insertion sort is better for small arrays; library sorts for everything else. The odd-even parallel variant is the one narrow exception.
Why is it called bubble sort? Large elements rise to the end of the array one position at a time, like bubbles in water.
Is it stable? Yes, provided you swap only on a strict inequality.
What is the best case? O(n) with the early-exit flag, on already-sorted input.
How does it compare with selection sort? Same complexity. Selection sort does fewer swaps (n total) and more comparisons, and it is not stable.
What does Python use? Timsort — a stable merge sort that detects existing sorted runs, with insertion sort for small ones.
Recap in one screen
Compare adjacent pairs and swap; each pass places one more element at the end.
Early exit gives O(n) on sorted input; otherwise O(n²) because elements move one step at a time.
Stable, in place, and dominated by insertion sort in every practical respect.
Its value is pedagogical: it makes the cost of single-step movement visible, which motivates faster algorithms.
Comb and cocktail variants let elements travel further; the odd-even variant is the one that parallelises.
Run it in Python
One line printed per pass, so you can watch the largest value reach the end of the list on pass one and stay there. The second run shows what the early exit is worth.
bubble_sort.pyPython 3
# Bubble sort: repeatedly swap adjacent items that are out of order.
def bubble_sort(a):
a = a[:] # copy, so the original stays printable
n = len(a)
passes = swaps = 0
for i in range(n - 1):
passes += 1
swapped = False
for j in range(n - 1 - i): # the last i items are already final
if a[j] > a[j + 1]:
a[j], a[j + 1] = a[j + 1], a[j]
swaps += 1
swapped = True
print(f"pass {passes}: {a}")
if not swapped: # a clean pass means it is sorted
break
return a, passes, swaps
data = [5, 1, 4, 2, 8, 0, 2]
print("start :", data)
out, passes, swaps = bubble_sort(data)
print("sorted:", out)
print(f"{passes} passes, {swaps} swaps")
print()
print("already sorted:")
_, p, s = bubble_sort([0, 1, 2, 4, 5, 8])
print(f"{p} pass, {s} swaps - the early exit makes the best case O(n)")
print()
print("reversed (the worst case):")
_, p, s = bubble_sort([8, 5, 4, 2, 1, 0])
print(f"{p} passes, {s} swaps")
Output
How the code works
for j in range(n - 1 - i):The - i is the optimisation that makes bubble sort worth writing. After pass i the last i items are in final position, so re-scanning them is pure waste.
a[j], a[j + 1] = a[j + 1], a[j]Python's tuple assignment evaluates the right side first, so this is a genuine swap. In most languages it needs a temporary variable, and forgetting it overwrites one of the two values.
if not swapped: breakA whole pass with nothing out of order proves the list is sorted. This single flag turns the best case from O(n²) into O(n) — and it is the only reason bubble sort beats selection sort on nearly-sorted input.
swapsThe swap count equals the number of inversions in the input, exactly. That is a real property, not an approximation: each swap fixes one inverted pair and no more.
Change one thing
Sort [1, 2, 3, 4, 5, 0]. One small value at the wrong end costs a full n passes — bubble sort moves items left one position per pass, and that is its real weakness.
Delete - i from the inner range. The result stays correct and the swap count is unchanged; only the wasted comparisons go up.
Change > to >=. Still sorted, but equal items now get swapped — the sort is no longer stable.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.
Check yourself
0 of 3
Answer without scrolling back up.
What does the swapped flag buy?
A pass with no swaps proves the list is sorted, so it stops. Without it, sorted input still costs the full n passes.
Why does the inner loop run to n - 1 - i rather than n - 1?
Each pass carries the largest remaining value to the end, so that tail never needs looking at again. It saves comparisons, not complexity.
The program's swap count for a given list equals:
Each swap fixes exactly one inverted pair, so the totals match exactly. That is why [1,2,3,4,5,0] is so expensive - one item out of place at the wrong end is five inversions.
Cheat sheet
Bubble Sort
Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted. The algorithm gets its name because smaller or larger elements "bubble" to their proper place.
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.