Expecting an O(n) Best Case From a Bubble Sort Without the Early Exit

Without a check for a pass with no swaps, sorted input still costs every comparison.

Bubble sort's O(n) best case comes from one check, stopping after a pass that made no swaps, and an implementation without that check makes every comparison even on input that is already sorted. This card shows the two versions side by side on five sorted numbers.

The symptom is a sort that is no faster on sorted data than on shuffled data of the same size, although every table of costs promised it would be. The version below is the one many people write first: two loops and a swap, and nothing else.

bubble_no_exit.pypy

def bubble_sort(items: list[int]) -> int:
    comparisons = 0
    for end in range(len(items) - 1, 0, -1):
        for j in range(end):
            comparisons += 1
            if items[j] > items[j + 1]:
                items[j], items[j + 1] = items[j + 1], items[j]
    return comparisons


print("comparisons on 1 2 3 4 5:", bubble_sort([1, 2, 3, 4, 5]))

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

comparisons on 1 2 3 4 5: 10

Without the early exit: every pass runs, whatever the input

It printed 10: four comparisons in the first pass, then three, two and one, every one of them on items already in order. The outer loop runs its n − 1 passes because nothing tells it to stop. The fix is a flag, reset at the start of each pass, set by any swap, and tested once the pass is over.

bubble_early_exit.pypy

def bubble_sort(items: list[int]) -> int:
    comparisons = 0
    for end in range(len(items) - 1, 0, -1):
        swapped = False
        for j in range(end):
            comparisons += 1
            if items[j] > items[j + 1]:
                items[j], items[j + 1] = items[j + 1], items[j]
                swapped = True
        if not swapped:
            break
    return comparisons


print("comparisons on 1 2 3 4 5:", bubble_sort([1, 2, 3, 4, 5]))

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

comparisons on 1 2 3 4 5: 4

With the early exit: the first pass that swaps nothing ends the sort

It printed 4, the n − 1 comparisons of a single pass. Without the flag, the comparisons always total n(n − 1)/2, so the sort is O(n²) in every case, no better than selection sort. The gap grows with n: on 10,000 sorted items the version without the flag makes 49,995,000 comparisons, and the version with it makes 9,999.

A table that gives bubble sort an O(n) best case assumes the flag, so keep it in any bubble sort you write, and before you quote a best case for any algorithm, check that the code in front of you has the check that earns it.

On the Algorithms: Searching and Simple Sorting cheatsheet

← → move through sections and cards