Bubble Sort

The Core Invariant: Floating Maximums Rightward

Imagine walking left-to-right across an array while comparing only adjacent pairs (a[j], a[j + 1]). Whenever the left value is strictly greater (a[j] > a[j + 1]), you swap them immediately.

What happens to the largest number in the unsorted region during that single pass? Once the cursor reaches that maximum element, it wins every comparison to its right and gets carried all the way to the last unsorted slot n - 1 - i.

After i outer passes:

• The suffix a[n - i .. n - 1] contains the i largest elements of the array in final sorted order.
• Pass i + 1 never needs to inspect those locked tail slots again.

Why Naive Bubble Sort Wastes Work — And How One Boolean Fixes It

Standard textbook Bubble Sort runs all n - 1 passes blindly, performing n(n - 1) / 2 comparisons even if you hand it [10, 14, 19, 27, 38].

Yet an array is sorted if and only if it contains zero adjacent inversions (a[j] > a[j + 1]). By tracking swapped = False at the start of each pass:

1. If any adjacent pair swaps, set swapped = True.
2. If an entire pass finishes with swapped == False, zero inversions exist anywhere in the prefix, so we break immediately!

Even better: you can record the index of the last swap (last_swap). Every element beyond last_swap was already in non-decreasing order, shrinking the next pass bound even faster than n - 1 - i.

Clean Python Implementation

def bubble_sort(nums: list[int]) -> list[int]:
    """In-place, stable Optimised Bubble Sort with last-swap boundary tightening."""
    n = len(nums)
    unsorted_end = n - 1

    while unsorted_end > 0:
        last_swap = 0
        for j in range(unsorted_end):
            # Strict '>' keeps equal elements in original order (stable)
            if nums[j] > nums[j + 1]:
                nums[j], nums[j + 1] = nums[j + 1], nums[j]
                last_swap = j
        # Everything after last_swap needed zero swaps and is already final
        unsorted_end = last_swap

    return nums

Complexity & Trade-Off Summary

Rabbits vs. Turtles: Large elements (“rabbits”) rocket to the right in a single pass, whereas a tiny element near the end (“turtle”, like 1 at a[n - 1]) only moves left by one slot per pass — motivating Insertion Sort and Shell/Comb Sort.