Bubble Sort

Bubble sort is one of the simplest sorting algorithms to learn, and a great first stop for understanding how comparison-based sorting works. It repeatedly walks through a list, compares each pair of neighboring elements, and swaps them if they are in the wrong order. Large values “bubble” toward the end of the list with every pass, which is where the name comes from. It is rarely the right choice for production code because faster algorithms exist, but its simplicity makes the mechanics of sorting, and the reasoning behind Big-O complexity, much easier to see clearly.

Overview / How It Works

Imagine you are handed a row of five playing cards face up, and you want to sort them from lowest to highest using only one rule: you may compare two cards that are next to each other, and swap them if the left one is bigger than the right one. Bubble sort is exactly this process, automated. You scan left to right across the row. Every time you find a pair out of order, you swap them immediately, then keep scanning. By the time you reach the end of the row, the single largest card is guaranteed to have been pushed all the way to the rightmost position: it either was compared and swapped forward every time it was the larger of a pair, or it started there already.

That observation, that the largest remaining element always reaches its final resting place after one full pass, is the key to how bubble sort makes progress. After the first pass, the last position is correct and never needs to be touched again. After the second pass, the last two positions are correct. In general, after k passes, the last k elements are in their final sorted positions, so each subsequent pass only needs to scan a slightly shorter prefix of the list. This is why the inner loop’s range shrinks as the outer loop variable i increases: it skips re-checking the tail that has already settled.

A plain implementation always performs n - 1 full passes regardless of how sorted the input already is. A small but important optimization tracks whether any swap happened during a pass; if a full pass completes with zero swaps, the list must already be sorted, and the algorithm can stop early. This turns the best case, an already-sorted list, into a single O(n) pass instead of a wasted O(n2) grind, which is why the “optimized” version below is worth knowing, not just the textbook one.

Time and Space Complexity

Bubble sort’s cost comes entirely from comparisons and swaps between adjacent elements. In the worst and average cases, every pair on every pass has to be checked, so the number of comparisons grows quadratically with input size.

Case Time Complexity Why
Best O(n) List is already sorted; with the swapped-flag optimization, one full pass finds no swaps and exits immediately.
Average O(n^2) Elements are in random order, so roughly half of all adjacent pairs are out of order on each of the ~n passes.
Worst O(n^2) List is sorted in reverse order; every pass finds an out-of-order pair, requiring the maximum n(n-1)/2 comparisons and swaps.

Space complexity is O(1): bubble sort sorts the list in place, swapping elements within the original list using only a constant number of extra variables (like a temporary holder during a swap), regardless of how large n is. It does not allocate a new list or use recursion, which is one of its few genuine advantages over algorithms like merge sort, which needs O(n) extra space.

Examples

Example 1: Basic Bubble Sort

def bubble_sort(arr: list[int]) -> list[int]:
    n = len(arr)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

numbers = [5, 2, 9, 1, 5, 6]
print(bubble_sort(numbers))

Output:

[1, 2, 5, 5, 6, 9]

The outer loop runs i from 0 to 4. On the first pass, comparing neighbors left to right, 5 and 2 swap, then the new 5 and 9 do not swap, then 9 and 1 swap, then 9 and 5 swap, then 9 and 6 swap, leaving 9 correctly placed at the end. Each subsequent pass repeats this on a shorter unsorted prefix until the whole list, [1, 2, 5, 5, 6, 9], is sorted. Notice the two 5s: they never swap past each other because the comparison is strictly >, so their original relative order is preserved.

Example 2: Optimized Bubble Sort With Early Exit

def bubble_sort_optimized(arr: list[int]) -> tuple[list[int], int]:
    n = len(arr)
    passes = 0
    for i in range(n - 1):
        passes += 1
        swapped = False
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr, passes

data = [1, 2, 3, 5, 4]
sorted_data, passes = bubble_sort_optimized(data)
print(sorted_data)
print(f"Passes: {passes}")

Output:

[1, 2, 3, 4, 5]
Passes: 2

The list starts almost sorted, only 5 and 4 are swapped. Pass one fixes that single swap and sets swapped = True. Pass two scans the remaining prefix, finds nothing out of order, leaves swapped as False, and the function breaks out immediately instead of running the two remaining passes an unoptimized version would perform. This is the early-exit optimization turning a near-best-case input into close to O(n) work.

Example 3: Sorting Records by a Key (and Why Stability Matters)

def bubble_sort_by_key(items: list[tuple[str, int]]) -> list[tuple[str, int]]:
    n = len(items)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if items[j][1] > items[j + 1][1]:
                items[j], items[j + 1] = items[j + 1], items[j]
                swapped = True
        if not swapped:
            break
    return items

students = [("Amir", 82), ("Bea", 91), ("Cy", 75), ("Dee", 91)]
print(bubble_sort_by_key(students))

Output:

[('Cy', 75), ('Amir', 82), ('Bea', 91), ('Dee', 91)]

This is a more realistic use case: sorting student records by score. Watch what happens to Bea and Dee, who both scored 91. During the very first comparison involving them, 91 > 91 is False, so they are never swapped relative to each other, and Bea (who appeared first in the input) still appears before Dee in the output. This demonstrates that bubble sort is a stable sort as long as the comparison uses strict >: equal elements keep their original relative order.

How It Works Step by Step

Trace [5, 1, 4, 2, 8] through the basic algorithm by hand:

Pass Comparisons (left, right) Array after pass
1 (5,1) swap, (5,4) swap, (5,2) swap, (5,8) no swap [1, 4, 2, 5, 8]
2 (1,4) no swap, (4,2) swap, (4,5) no swap [1, 2, 4, 5, 8]
3 (1,2) no swap, (2,4) no swap [1, 2, 4, 5, 8] (no swaps)
4 (1,2) no swap [1, 2, 4, 5, 8]

Two things are worth noticing. First, after pass 1 the largest value, 8, is already correctly placed at the end, even though it was never moved, because it started as the maximum of the whole list. Second, pass 3 makes zero swaps: an optimized implementation with the swapped flag would stop right there instead of running the useless pass 4, saving one full comparison for a tiny cost here, but a much bigger saving on longer, nearly-sorted inputs.

Common Mistakes

Mistake 1: Off-by-one inner loop bound causing an IndexError

A very common bug is letting the inner loop’s j reach the last index, so that arr[j + 1] reaches past the end of the list:

def bubble_sort_buggy(arr):
    n = len(arr)
    for i in range(n - 1):
        for j in range(n):  # BUG: should be range(n - 1 - i)
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

print(bubble_sort_buggy([3, 1, 2]))

When j reaches n - 1 (the last valid index), the code tries to read arr[j + 1], which is out of bounds, and Python raises IndexError: list index out of range. The inner range must stop one short of the unsorted region’s end, and shrink further as i grows so it never re-scans the already-sorted tail:

def bubble_sort_fixed(arr: list[int]) -> list[int]:
    n = len(arr)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

print(bubble_sort_fixed([3, 1, 2]))

Output:

[1, 2, 3]

Mistake 2: Forgetting that bubble sort mutates the list in place

Because bubble_sort both sorts arr in place and returns it, it is easy to assume you are getting back a brand-new sorted list while the original is untouched. That assumption is wrong:

def bubble_sort(arr: list[int]) -> list[int]:
    n = len(arr)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

original = [3, 1, 2]
result = bubble_sort(original)
print(original)
print(result)
print(original is result)

Output:

[1, 2, 3]
[1, 2, 3]
True

original was mutated as a side effect, and result is literally the same list object (original is result prints True), not a copy. If you need to keep the original order intact, copy the list before sorting:

def bubble_sort_copy(arr: list[int]) -> list[int]:
    arr = arr.copy()
    n = len(arr)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

original = [3, 1, 2]
result = bubble_sort_copy(original)
print(original)
print(result)

Output:

[3, 1, 2]
[1, 2, 3]

Mistake 3: Using >= instead of >, which breaks stability

It is tempting to write the comparison as >=, thinking it makes no difference. It does: it forces a swap between elements that are already equal, silently reversing their original order.

def bubble_sort_unstable(items: list[tuple[str, int]]) -> list[tuple[str, int]]:
    n = len(items)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if items[j][1] >= items[j + 1][1]:
                items[j], items[j + 1] = items[j + 1], items[j]
    return items

pairs = [("Bea", 91), ("Dee", 91)]
print(bubble_sort_unstable(pairs))

Output:

[('Dee', 91), ('Bea', 91)]

Bea was first in the input, but the unnecessary swap on the equal pair flips her behind Dee. Sticking to a strict > comparison avoids swapping equal elements, keeping the sort stable:

def bubble_sort_stable(items: list[tuple[str, int]]) -> list[tuple[str, int]]:
    n = len(items)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if items[j][1] > items[j + 1][1]:
                items[j], items[j + 1] = items[j + 1], items[j]
    return items

pairs = [("Bea", 91), ("Dee", 91)]
print(bubble_sort_stable(pairs))

Output:

[('Bea', 91), ('Dee', 91)]

Best Practices

  • Reach for bubble sort only for teaching, very small lists, or data you already know is nearly sorted, where the early-exit optimization keeps it close to O(n).
  • Always implement the swapped-flag early exit; there is no good reason to run the unoptimized textbook version once you understand the improvement.
  • For real production code, use Python’s built-in sorted() or list.sort() (Timsort), which is O(n log n) average and worst case and is stable. Bubble sort should not appear in code you ship.
  • If you specifically need a simple, in-place algorithm for very small or constrained inputs, insertion sort usually beats bubble sort: it does fewer writes and adapts better to nearly-sorted data.
  • When the relative order of equal elements matters (stability), always compare with strict > or <, never >= or <=.
  • Remember that bubble sort mutates its input in place; copy the list first with arr.copy() if you need to keep the original order.

Practice Exercises

1. Count the swaps. Write a function that sorts a list with bubble sort and also returns the total number of swaps it performed. Test it on [5, 4, 3, 2, 1] and on [1, 2, 3, 4, 5], and compare the counts. Hint: add a counter alongside the swapped boolean.

2. Sort in descending order. Modify the basic bubble sort so it sorts a list from highest to lowest by changing only the comparison operator. Check your work: sorting [4, 2, 7, 1] in descending order should produce [7, 4, 2, 1].

3. Implement cocktail shaker sort. This bubble sort variant alternates direction on each pass: left-to-right, then right-to-left, then left-to-right again, and so on, using the swapped flag to stop early. Implement it, then explain in a comment why alternating direction can move a small value stuck near the end of the list (sometimes called a “turtle”) into place faster than plain bubble sort would.

Summary

  • Bubble sort repeatedly compares and swaps adjacent out-of-order elements, letting the largest unsorted element “bubble” to its correct position on every pass.
  • Time complexity: O(n) best case (already sorted, with the early-exit optimization), O(n^2) average case, O(n^2) worst case (reverse-sorted input).
  • Space complexity: O(1), since it sorts the list in place using only a constant amount of extra memory.
  • Bubble sort is stable, equal elements keep their relative order, as long as the comparison uses strict > rather than >=.
  • It is a teaching algorithm, not a production one; Python’s built-in sorted() and list.sort() (Timsort, O(n log n)) should be used for real code.
  • Watch for three recurring bugs: an off-by-one inner-loop bound causing an IndexError, forgetting that the input list is mutated in place, and using >= instead of >, which silently breaks stability.