Sorting Algorithm

Bubble Sort

“The Participation Trophy”

Time: O(n²)

Space: O(1)

History

Bubble Sort is likely the first algorithm every developer learns, and the first one they are told to stop using. Its origins are in the 1950s, named for the way large elements "bubble" to the top of the list like carbonation in a soda. Donald Knuth famously remarked that "the bubble sort seems to have nothing to recommend it, except a catchy name."

Despite the criticism, it remains the standard "Hello World" of algorithm classes because its logic maps 1:1 with how a human might inefficiently sort a deck of cards if they were tired.

How It Works

The algorithm works by frantically comparing neighbors. It steps through the list, looks at two adjacent items, and swaps them if they are in the wrong order. It repeats this until the list is clean.

The Algorithm Step-by-Step

Scan: Start at index 0.
Compare: Look at item $i$ and item $i+1$ .
Swap: If the one on the left is bigger, swap them.
Repeat: Do this for every pair in the list.
Loop: Go back to the start and do it all again until you finish a pass without making a single swap.

The "Bubbling" Effect

After the first pass, the largest number is guaranteed to be at the very end. After the second pass, the second largest is locked in. The sorted portion grows from right to left.

Optimization (The Early Exit)

The only redeeming quality of Bubble Sort is that if you pass through the list and swap nothing, you know you're done. This makes it surprisingly fast for lists that are *almost* sorted.

Best CaseO(n)

If the array is already sorted, it does one 'sanity check' pass, realizes no swaps are needed, and quits early.

Worst CaseO(n²)

If the array is reverse sorted, it has to move every single element across the entire array, one step at a time.

Average CaseO(n²)

On random data, it's slow. Very slow. It performs a quadratic number of comparisons and swaps.

SpaceO(1)

It sorts in-place. We only need a tiny bit of memory to store the temporary variable for swapping.

Code Walkthrough

Real implementations in multiple programming languages. Select a language to view idiomatic code.

1def bubble_sort(arr: list[int]) -> None:
2    """Sort array in-place using bubble sort."""
3    n = len(arr)
4
5    for i in range(n - 1):
6        swapped = False
7
8        for j in range(n - 1 - i):
9            if arr[j] > arr[j + 1]:
10                arr[j], arr[j + 1] = arr[j + 1], arr[j]
11                swapped = True
12
13        # Early exit if no swaps occurred
14        if not swapped:
15            break

Python • .py

Real World Use Cases

1Computer Science 101 classes
2Testing if a list is already sorted (sanity checks)
3Tiny datasets (less than 50 items)
4Computer Graphics (where swapping neighbors looks cool)

Key Insights

It is stable (doesn't reorder equal items).
It is adaptive (fast if data is nearly sorted).
It is easy to implement (hard to introduce bugs).
It is theoretically arguably the worst general-purpose sort.

When to Use

Use it when you are teaching someone to code, or if you need to quickly check if a list is already sorted. It's also fine for lists so small that the CPU doesn't care.