Bubble Sort in Python With Step-by-Step Examples and Complexity Notes

Bubble sort repeatedly walks through a list, compares neighbors, and swaps them when they are out of order. The largest values “bubble” toward the end after each pass. It is rarely the right choice for production datasets, but it is one of the clearest ways to learn how comparison sorts behave—and interviewers still use it to test whether you understand loops, invariants, and big-O reasoning.

How the algorithm works

Given a list of comparable items:

1. Compare index i and i+1.
2. If the left item is greater than the right, swap them.
3. Move one position right and repeat until the unsorted portion ends.
4. After each full pass, the next-largest item is locked at the tail.
5. Repeat for a shrinking prefix until no swaps occur.

For n items, a naive implementation may need up to n-1 passes and about n² comparisons in the worst case.

Basic Python implementation

def bubble_sort(values: list) -> list:
    items = values.copy()
    n = len(items)
    for pass_num in range(n - 1):
        for i in range(n - 1 - pass_num):
            if items[i] > items[i + 1]:
                items[i], items[i + 1] = items[i + 1], items[i]
    return items

if __name__ == "__main__":
    sample = [5, 1, 4, 2, 8]
    print(bubble_sort(sample))  # [1, 2, 4, 5, 8]

This version sorts ascending using Python’s default comparison. For custom objects, pass a key function or implement rich comparison on the class.

Trace: [5, 1, 4, 2, 8]

Pass 1

• Compare 5 and 1 → swap → [1, 5, 4, 2, 8]
• Compare 5 and 4 → swap → [1, 4, 5, 2, 8]
• Compare 5 and 2 → swap → [1, 4, 2, 5, 8]
• Compare 5 and 8 → no swap

Largest value 8 is already at the end; inner loop can ignore last index next pass.

Pass 2 fixes 5 into place; Pass 3 fixes 4; after enough passes the list is sorted.

Tracing on paper is tedious but builds intuition for why inner loop bounds shrink.

Early exit optimization

If a complete pass performs no swaps, the list is sorted—stop early:

def bubble_sort_optimized(values: list) -> list:
    items = values.copy()
    n = len(items)
    for pass_num in range(n - 1):
        swapped = False
        for i in range(n - 1 - pass_num):
            if items[i] > items[i + 1]:
                items[i], items[i + 1] = items[i + 1], items[i]
                swapped = True
        if not swapped:
            break
    return items

Best case (already sorted): O(n) comparisons with this optimization. Worst case (reverse sorted): still O(n²).

Complexity summary

Space: O(1) extra if sorting in place (the examples above copy the input to avoid mutating callers; in-place sorting drops that copy).

Stability: Bubble sort is stable if you only swap when strictly greater (> not >=), so equal keys keep their relative order—useful in multi-key sorting tutorials.

When bubble sort is the wrong tool

Python’s sorted() uses Timsort—O(n log n) in the worst case and highly tuned for real data. For numeric arrays, NumPy sort or dedicated libraries beat handwritten bubbles by orders of magnitude.

Use bubble sort to teach or interview, not to sort millions of rows in production.

Variants worth mentioning

• Cocktail shaker sort alternates left-to-right and right-to-left passes; slightly better on some “almost sorted” patterns but still quadratic worst case.
• Bidirectional bubble — same family; know the name if it appears in coursework.

Practice exercises

1. Sort descending by flipping the comparison operator.
2. Count how many swaps occur for a given input—connects to inversion counts in harder sorts.
3. Add a key=lambda x: ... parameter like built-in sorted.
4. Sort a list of dicts by a numeric field without using sorted—good stepping stone to itemgetter.

FAQ

Is bubble sort ever used in real systems?
Almost never for general sorting. Tiny embedded lists or educational firmware might use it; everything else reaches for better algorithms.

Why learn it if sorted() exists?
It teaches loop invariants, stability, and how to reason about quadratic growth—skills that transfer to optimizing real bottlenecks elsewhere.

Can bubble sort run on linked lists?
Yes, but swapping nodes is clumsier than with arrays; other O(n²) sorts like insertion sort are often taught with lists instead.

How does Python’s sort differ?
Timsort exploits existing order in data; bubble sort does not adapt beyond the early-exit trick.

Bubble sort in Python takes minutes to implement and hours to fully appreciate. Code it once, optimize for early exit, analyze complexity, then reach for sorted() when the job is real.