Bubble Sort

Overview

Bubble Sort is a comparison-based sorting algorithm that walks the array from one end to the other, comparing each pair of adjacent elements and swapping them if they are out of order. One such walk is called a pass. The algorithm keeps making passes until it completes one in which no swap was needed, at which point the array must be sorted, because no adjacent pair is out of order and adjacency covers every ordering relation in the sequence.

The name refers to the way each pass carries the largest still-unsorted element to its final position at the end of the array, the way a bubble rises through liquid. The name is slightly misleading: after k passes, the k largest elements are locked into the tail of the array, but the smaller elements do not travel very far in a single pass. That asymmetry is the whole reason for the O(n²) worst case, a small element trapped at the wrong end of the array can move only one position per pass, so an array sorted in reverse takes almost exactly n passes to fix.

Bubble sort is the shortest correct comparison sort you can write. In four lines of pseudocode it is stable (equal elements never swap past each other), in-place (uses only a handful of extra variables regardless of input size), and adaptive when written with the early-termination check, a nearly-sorted array runs in almost linear time. Very few algorithms package that many properties into so little code. That is why it survives in textbooks and introductory courses despite being one of the slowest general-purpose sorts ever devised.

History and Where the Name Comes From

The idea of sorting a sequence by exchanging out-of-order neighbours is older than computing, it is essentially how you would sort a hand of playing cards by making repeated left-right sweeps. In the computing literature the technique appears under several names before "bubble sort" is settled on: Iverson's A Programming Language (1962) refers to it as an exchange sort, and early IBM manuals variously call it sinking sort, sifting sort, and ripple sort. Each name captures a different mental model of the same mechanic: are the large elements sinking to the bottom, or the small ones rising to the top?

Knuth's The Art of Computer Programming, Volume 3 (1973) is the source most later textbooks trace their treatment to. Knuth is famously unimpressed, his verdict is that bubble sort "seems to have nothing to recommend it, except a catchy name and the fact that it leads to some interesting theoretical problems." That line, softened over the decades, is why modern courses often introduce bubble sort in the same breath as an explanation of why not to use it. The rehabilitation attempts, there have been several, usually turn on the algorithm's clarity as a teaching tool, not its performance.

The name "bubble sort" itself is documented in the ACM literature from the early 1960s and had become the standard English-language term by the time the first generation of computer science textbooks was written in the mid-1970s. Other traditions retain the older names: German and Russian textbooks still often prefer Sortieren durch Vertauschen and Сортировка пузырьком (exchange sort, bubble sort) as parallel terms.

How It Works

The algorithm works by:

1. Comparing adjacent elements in the array
2. Swapping them if they are in the wrong order (ascending or descending)
3. Repeating this process for each pair of adjacent elements
4. Continuing until no more swaps are needed

With each complete pass through the array, the largest unsorted element "bubbles up" to its correct position at the end of the array.

Algorithm

BubbleSort(arr):
    n = length of arr
    for i = 0 to n - 1:
        swapped = false
        for j = 0 to n - i - 2:
            if arr[j] > arr[j + 1]:
                swap arr[j] and arr[j + 1]
                swapped = true
        if swapped == false:
            break  # Array is already sorted
                

Implementation

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        # If no swaps occurred, array is sorted
        if not swapped:
            break
    return arr
                

Complexity Analysis

• Time Complexity:
  • Best Case: O(n) - when array is already sorted (with optimization)
  • Average Case: O(n²)
  • Worst Case: O(n²) - when array is sorted in reverse order
• Space Complexity: O(1) - only uses a constant amount of extra space

The nested loops result in O(n²) comparisons in the worst case. The optimization that checks if any swaps occurred allows the algorithm to terminate early if the array is already sorted, giving O(n) best case.

Characteristics

• Stable: Yes - equal elements maintain their relative order
• In-place: Yes - only requires O(1) extra space
• Adaptive: Yes - can detect if array is already sorted
• Online: No - requires the entire array to be present

Performance in Practice

Textbook complexity says bubble sort is O(n²) and mergesort is O(n log n), which suggests mergesort should win at all but the tiniest sizes. The measured story is more interesting.

For arrays of fewer than roughly 8–16 elements, bubble sort routinely outperforms mergesort on modern hardware. The reason is that constants dominate at small n. Mergesort's recursive structure has real overhead, function call setup, stack allocation, the merge step's auxiliary array, while bubble sort is a pair of nested loops with a single conditional swap. The memory access pattern is strictly sequential and forward-only, which is close to the best possible profile for CPU prefetching and cache line utilisation. Every element read fits neatly into the L1 cache path the hardware was already preparing for you.

Its weakness is not the number of comparisons per se, O(n²) is fine at small n, but the number of swaps. Insertion sort makes O(n²) comparisons but only O(n²/4) swaps on average, because it shifts elements instead of exchanging them. Bubble sort performs a full swap for every misordered pair it encounters, which is why insertion sort is almost always the preferred choice in practice for the tiny-array case. Every hybrid production sort that bottoms out on a small-array specialisation, Timsort, introsort, pdqsort, picks insertion sort, not bubble sort, for that role.

On the nearly-sorted end of the spectrum bubble sort with early termination is genuinely fast: a single pass with zero swaps confirms the array is sorted, so an already-sorted array of n elements takes exactly n−1 comparisons and terminates. This is why bubble sort is sometimes used inside embedded controllers that sort a small buffer of sensor readings that were almost certainly monotonic to begin with.

Variants and Cousins

Several algorithms are best understood as small modifications of bubble sort's basic mechanic.

Cocktail Shaker Sort (Bidirectional Bubble Sort)

On each iteration, walk the array left-to-right (carrying the largest unsorted element to the right end) then right-to-left (carrying the smallest to the left end). This addresses bubble sort's biggest asymmetry, the fact that a small element trapped at the end of the array can only move one position per left-to-right pass. Cocktail sort is still O(n²) in the worst case, but for arrays that are "sorted except for one element far from its target" (sometimes called turtles) it can be several times faster than plain bubble sort.

Comb Sort

A more substantial improvement, published by Włodzimierz Dobosiewicz in 1980. Instead of comparing adjacent elements (gap 1), comb sort starts with a large gap, typically n/1.3, and shrinks it on each pass, finishing with a plain bubble-sort pass at gap 1. The large early gaps let elements move much further per swap, killing the "turtle" problem in log(n) time. Comb sort has O(n²) worst case but empirically behaves close to O(n log n) on random data, a rare example of a simple bubble-sort-family algorithm that is genuinely usable.

Odd-Even Sort (Brick Sort)

Bubble sort's inner loop has a sequential dependency, each swap must complete before the next comparison begins, which makes it awkward to parallelise. Odd-even sort splits each pass into two phases: compare-and-swap all pairs at odd indices, then all pairs at even indices. Within each phase the comparisons are independent and can be run in parallel across many processors or GPU threads. This makes odd-even sort a natural fit for hardware sorting networks and certain SIMD implementations, though its O(n²) work total means it is only competitive when you have enough parallelism to hide the extra comparisons.

Common Misconceptions

Bubble sort is often the first algorithm people learn and the first they misremember. A few corrections worth stating explicitly.

• "Bubble sort places one element in its final position per pass" is half-right. It places one element from the unsorted end per pass, the largest remaining element goes to the current end of the unsorted region. The smaller elements are left roughly where they were, shifted by at most one position each. Reversing the array on input is the worst case precisely because the small elements have furthest to travel.
• "With the early-termination optimisation, bubble sort is O(n) average case" is wrong. The best case is O(n), on an already-sorted array, one pass with zero swaps confirms sortedness. On random input, the expected number of misordered adjacent pairs on pass k is proportional to n−k, so the average total work is O(n²) with or without early termination.
• "Bubble sort is stable" depends on how you write it. The standard version with if arr[j] > arr[j+1]: swap is stable, because it never swaps equal elements. Writing >= instead of > breaks stability by swapping equal elements needlessly, a subtle bug worth being aware of if you are implementing bubble sort against a stability requirement.
• "The inner loop should run from 0 to n" misses the standard optimisation. After k passes, the last k elements are already in their final positions, so the inner loop can stop k elements before the end. That change alone cuts the number of comparisons roughly in half.

When to Use Bubble Sort

The honest answer, in modern general-purpose programming, is almost never. If you find yourself reaching for a sort in production Python, list.sort() is Timsort and is O(n log n), stable, and highly optimised. In C++ it is std::sort, which is introsort. In Java it is a merge sort variant for objects. Every one of those beats bubble sort by orders of magnitude on realistic inputs while asking nothing of you.

That leaves a small handful of genuine use cases:

• Teaching and code review clarity. When you want the reader of your code to see immediately that a sort is happening and correctness is more important than speed, say, sorting three or four items in a test fixture, a five-line bubble sort is easier to read than a call into a library you have to trust.
• Extremely constrained embedded systems. On microcontrollers where every byte of program memory counts, the compiled size of bubble sort is often smaller than the call overhead of a general-purpose sort. Some AVR and PIC codebases still use it deliberately for this reason.
• Sorting almost-sorted streams. If you know your data is either sorted or one swap away from sorted, a single-pass bubble check followed by exit is optimal, you cannot do better than "look at every element once."
• Sorting networks and parallel hardware. Odd-even sort (a bubble sort variant) is embarrassingly parallel and is used in some GPU compute kernels and hardware sorting circuits, where the O(n²) work is amortised across many parallel processing elements.

Outside these niches, reach for insertion sort when the array is small, quicksort or introsort for general use, and mergesort when stability or worst-case guarantees matter.

Example

Sorting [64, 34, 25, 12, 22, 11, 90]:

Pass 1: [34, 25, 12, 22, 11, 64, 90]  (64 and 90 are in correct positions)
Pass 2: [25, 12, 22, 11, 34, 64, 90]  (34 is in correct position)
Pass 3: [12, 22, 11, 25, 34, 64, 90]  (25 is in correct position)
Pass 4: [12, 11, 22, 25, 34, 64, 90]  (22 is in correct position)
Pass 5: [11, 12, 22, 25, 34, 64, 90]  (12 is in correct position)
Pass 6: [11, 12, 22, 25, 34, 64, 90]  (No swaps, array is sorted)
                

Related Algorithms

Explore other sorting algorithms:

• Merge Sort - Divide and conquer with O(n log n) guarantee
• Quick Sort - Fast average case performance
• Heap Sort - In-place O(n log n) sorting
• Back to Sorting Algorithms Overview