Bubble sort is often the first sorting algorithm you learn in a computer science course. It's not the fastest, but it's one of the most intuitive — and understanding it builds the foundation for understanding more advanced algorithms.

How Bubble Sort Works

The idea is beautifully simple: walk through the list, compare each pair of adjacent elements, and swap them if they're in the wrong order. Repeat until no more swaps are needed.

It's called "bubble" sort because larger elements "bubble up" to the end of the list with each pass, like bubbles rising in water.

Step by Step

Let's sort [5, 3, 8, 1, 2]:

Pass 1:

Compare 5 and 3: swap → [3, 5, 8, 1, 2]
Compare 5 and 8: no swap → [3, 5, 8, 1, 2]
Compare 8 and 1: swap → [3, 5, 1, 8, 2]
Compare 8 and 2: swap → [3, 5, 1, 2, 8]

After pass 1, the largest element (8) is in its final position.

Pass 2:

Compare 3 and 5: no swap → [3, 5, 1, 2, 8]
Compare 5 and 1: swap → [3, 1, 5, 2, 8]
Compare 5 and 2: swap → [3, 1, 2, 5, 8]

Now 5 is in its final position.

Pass 3:

Compare 3 and 1: swap → [1, 3, 2, 5, 8]
Compare 3 and 2: swap → [1, 2, 3, 5, 8]

Pass 4:

Compare 1 and 2: no swap → [1, 2, 3, 5, 8]

Sorted! No swaps in this pass, so we know we're done.

The Code

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break  # Already sorted!
    return arr

The swapped flag is an optimization: if no swaps happen in a complete pass, the list is already sorted and we can stop early.

Time Complexity

| Case | Complexity | When | |------|-----------|------| | Best | O(n) | Already sorted (with early termination) | | Average | O(n²) | Random order | | Worst | O(n²) | Reverse sorted |

Space complexity: O(1) — bubble sort sorts in-place, using only a constant amount of extra memory.

Why O(n²)?

In the worst case, we need n-1 passes, and each pass compares up to n-1 pairs. That's roughly n × n = n² comparisons.

For 10 elements, that's ~100 operations. Fine. For 1,000 elements, that's ~1,000,000 operations. Still okay. For 1,000,000 elements, that's ~1,000,000,000,000 operations. That could take hours.

This is why bubble sort is impractical for large datasets.

Properties of Bubble Sort

Stable: Equal elements maintain their relative order. If two students have the same grade, they'll stay in their original order after sorting.

In-place: Uses O(1) extra memory. No need to create a copy of the array.

Adaptive: With the early termination optimization, it runs in O(n) on already-sorted or nearly-sorted data.

Simple: Easy to understand, implement, and debug. The entire algorithm is about 10 lines of code.

When to Use Bubble Sort

Use it when:

You're learning about sorting algorithms (that's why it's taught first!)
The dataset is very small (< 50 elements)
The data is nearly sorted (the early termination makes it efficient)
You need a stable sort with minimal code

Don't use it when:

Performance matters (use quick sort or merge sort instead)
The dataset is large
The data is randomly ordered or reverse sorted

Bubble Sort vs Other Algorithms

| Algorithm | Best | Average | Worst | Stable? | In-place? | |-----------|------|---------|-------|---------|-----------| | Bubble Sort | O(n) | O(n²) | O(n²) | Yes | Yes | | Selection Sort | O(n²) | O(n²) | O(n²) | No | Yes | | Insertion Sort | O(n) | O(n²) | O(n²) | Yes | Yes | | Merge Sort | O(n log n) | O(n log n) | O(n log n) | Yes | No | | Quick Sort | O(n log n) | O(n log n) | O(n²) | No | Yes |

Insertion sort is often a better choice than bubble sort for small or nearly-sorted data — it's also O(n²) in the worst case but typically does fewer swaps.

Common Variations

Cocktail Shaker Sort: Instead of always going left-to-right, alternate between left-to-right and right-to-left passes. This helps elements that need to move in both directions.

Comb Sort: Instead of comparing adjacent elements, compare elements with a gap that shrinks over time. This addresses bubble sort's main weakness — small values at the end of the list ("turtles") that move very slowly.

See It In Action

Reading about bubble sort is one thing. Watching it happen is another.

Our interactive visualization lets you step through bubble sort one comparison at a time. You'll see elements light up as they're compared, watch swaps happen in real-time, and see the sorted portion grow with each pass. You can adjust the speed, change the array size, and compare it side-by-side with other sorting algorithms.

There's no faster way to build intuition for how sorting works.