How Bubble Sort Works

The outer loop calls reversed(range(length)), which iterates i from length-1 down to 0. The inner loop runs from j=0 to j=i-1, which means each outer pass considers one fewer comparison than the last: after the first pass, the largest element is guaranteed to be in its final position, so the inner loop can skip it. That shrinking bound takes the comparison count from n squared to n(n-1)/2, but the asymptotic class stays O(n squared). The swapped flag on lines 53 and 58 is what achieves the O(n) best case. If a full inner pass makes no swaps, the list is already sorted and the break on line 59 exits immediately. The already-sorted doctest on line 20 verifies that this path executes correctly.

The recursive variant is a different encoding of the same algorithm. Where the iterative version uses a break to exit early, this version uses the conditional at the tail: return collection if not swapped else bubble_sort_recursive(collection). One full forward pass runs in the body (lines 107 through 110), and the result of that pass determines whether another pass is needed. The function recurses on the same collection object, not a copy, so the list is modified in place across all recursive frames. The doctest battery mirrors the iterative version with one addition: line 94 tests a mixed-case ASCII list (['a', 'Z', 'B', 'C', 'A', 'c']) and shows that Python sorts uppercase letters before lowercase, which is a fact about ord() values rather than anything bubble sort does.

The forward pass on lines 107 through 110 always scans the full length - 1 adjacent pairs, regardless of how many swaps the previous call made. That is the structural difference from the iterative version, which shrinks the inner loop on each outer pass. The recursive version does more comparison work per level because it does not track how far the sorted suffix extends. In exchange, the code is six lines instead of ten, and the stopping condition is a single expression on line 112. The benchmark in the __main__ block below quantifies the cost of that trade-off with timeit over 10,000 runs. On random input, the iterative version is typically faster because fewer comparisons are needed in the final passes.

Most algorithm files in this repository end with a simple read-sort-print driver. This one adds a timeit benchmark. The benchmark passes unsorted[:] rather than unsorted to the sort function inside the timed string, because both sort functions mutate the collection in place and a reused sorted list would make every subsequent sort trivially fast. The slice copy is the correct control. Running python3 sorts/bubble_sort.py prints both sorted results and their timing across 10,000 runs, confirming the comment on line 122: iterative is slightly faster because it does fewer total comparisons. The imports of sample and timeit are inside the if __name__ block to avoid loading them when the module is imported by another file or by pytest.

Most files in sorts/ hold exactly one function. The contribution guide says identical reimplementations of an existing file are rejected, but variants that encode the same algorithm differently add value. The iterative and recursive forms of bubble sort make the same logical steps visible from two angles: one controls repetition with a loop counter and a break, the other with a tail call and a conditional return. Placing them side by side in the same file lets a reader compare them directly without switching files, and the timeit benchmark in __main__ gives a concrete measurement rather than a prose claim about which is faster. That pairing of two perspectives plus a benchmark is what separates this file from a single-function stub and justifies the larger doctest count. See the Sorting Algorithms category tour for the full set of variants across sorts/.