Bubble sort explained: how it works, code and complexity

The idea in plain words

Compare the first two elements. If the first is larger, swap them. Then compare the second and third, then the third and fourth, and so on to the end of the list. This is one pass. After the first pass, the largest element is guaranteed to be last, because every comparison carried it one step to the right.

Repeat the pass on the unsorted part, which shrinks by one element each time. If a whole pass makes no swaps, the list is sorted and you can stop early.

Worked example, pass by pass

Sort [5, 1, 4, 2, 8] in ascending order. Elements after the bar are in their final place.

Without the early exit, the algorithm would run a fourth pass. With it, three passes are enough here.

Python implementation

def bubble_sort(items):
    """Sort a list in place, ascending. Returns the same list."""
    n = len(items)
    for end in range(n - 1, 0, -1):     # last index of the unsorted part
        swapped = False
        for i in range(end):
            if items[i] > items[i + 1]:  # strict >, keeps equal items in order
                items[i], items[i + 1] = items[i + 1], items[i]
                swapped = True
        if not swapped:                  # no swaps: already sorted
            break
    return items
print(bubble_sort([5, 1, 4, 2, 8]))     # [1, 2, 4, 5, 8]
print(bubble_sort([3, 3, 1]))           # [1, 3, 3]
print(bubble_sort([]))                  # []

The inner loop stops at end because everything after it is already in place. The swapped flag gives the O(n) best case on sorted input.

Time and space complexity

For 10,000 elements in reverse order, that is almost 50 million comparisons and swaps. The number of swaps always equals the number of inversions, which are pairs of elements that are out of order.

How bubble sort compares with other sorts

Bubble sort is stable because it only swaps adjacent elements and only when they are strictly out of order, so equal elements never pass each other. Insertion sort has the same complexity and stability but in practice does fewer writes and is faster, which is why it, not bubble sort, is used inside hybrid algorithms such as Timsort.

Variants and common mistakes

• Cocktail shaker sort goes left-to-right and then right-to-left on alternating passes, which moves small elements at the end (called turtles) to the front faster. It is still O(n²).
• Comb sort compares elements a gap apart and shrinks the gap, which removes many turtles early; with gap 1 it becomes bubble sort.
• Odd-even transposition sort compares all odd pairs, then all even pairs, and is used to teach parallel sorting.

When to use bubble sort

Almost never in production code. In Python, call sorted(items) or items.sort(), which use Timsort, run in O(n log n) and are stable. Bubble sort is still useful to know because it is the simplest sort to explain, its proof of correctness is easy to follow, and it is a common first interview or exam question about loops, swaps and complexity.

The one practical advantage is detecting a sorted list in a single O(n) pass, but a plain loop that compares neighbours does that without sorting anything.