Bubble Sort

How bubble sort works

Walk through the array. For each adjacent pair, if the left element is greater than the right, swap them. After one pass, the largest element is at the end. Repeat with the remaining unsorted prefix. Repeat until no swaps happen on a full pass.

Why "bubble"? Each pass causes the largest remaining element to "bubble up" to its final position at the end. The same metaphor explains why each subsequent pass can ignore the last position — it's already locked in.

Concrete example. Sort [5, 1, 4, 2, 8]:

Pass 1: [1, 4, 2, 5, 8]   (5 bubbled to end)
Pass 2: [1, 2, 4, 5, 8]   (4 bubbled to position 2)
Pass 3: [1, 2, 4, 5, 8]   (no swaps — early exit)

The early-exit optimization

A naive bubble sort always runs n-1 passes regardless of the input. The fix is one extra boolean: track whether any swap happened on the current pass. If no swaps, the array is sorted — return.

// Naive — always O(n²)
function bubbleNaive(arr) {
  for (let i = 0; i < arr.length - 1; i++)
    for (let j = 0; j < arr.length - 1; j++)
      if (arr[j] > arr[j+1]) [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
  return arr;
}

// Optimized — O(n) on sorted input, O(n²) worst case
function bubbleOptimized(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let swapped = false;
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j+1]) {
        [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
        swapped = true;
      }
    }
    if (!swapped) return arr;
  }
  return arr;
}

Two improvements: the early-exit flag, and the inner loop's length - 1 - i bound (since the last i positions are already sorted from previous passes).

When to use bubble sort

• Teaching. The clearest expression of "compare adjacent, swap if out of order" — the conceptual core of comparison sorting.
• Tiny inputs you know are nearly sorted. With the early-exit optimization, an already-sorted check is O(n). A real sort would also be fast here, but if you're avoiding a library dependency, bubble sort is small.
• Embedded code with strict size constraints. Bubble sort's implementation is the smallest of any correct sort — useful when binary size matters more than runtime.

Use cases where bubble sort is wrong: anything user-facing, anything with n > ~50, anything you'd run on a server, anything where someone might benchmark you. Production code uses Timsort (Python, Java for objects), pdqsort (Rust), or quicksort variants.

Bubble sort vs other O(n²) sorts

	Bubble sort	Selection sort	Insertion sort
Time (worst)	O(n²)	O(n²)	O(n²)
Time (best)	O(n) optimized	O(n²)	O(n)
Space	O(1)	O(1)	O(1)
Stable	Yes	No (basic)	Yes
Swaps (worst)	O(n²)	O(n)	O(n²)
Real-world speed	Slowest	Slow	Fastest of three
Used as cutoff in std libs	No	No	Yes (n < ~16)

Insertion sort is the only one of the three that production sorting libraries use — as the cutoff for small subarrays inside a quicksort or merge-sort. Bubble sort never appears in production code.

Pseudo-code

function bubbleSort(arr):
    n = arr.length
    for i from 0 to n - 2:
        swapped = false
        for j from 0 to n - 2 - i:
            if arr[j] > arr[j+1]:
                swap arr[j] and arr[j+1]
                swapped = true
        if not swapped: return arr   # already sorted
    return arr

Python implementation

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:
            return arr
    return arr

Python's builtin sorted() uses Timsort, which is dramatically faster — about 100× on a million-element list. Use the builtin in any real code.

Common bugs and edge cases

• Inner loop bound off by one. The inner loop should run to n - 1 - i, not n. The last i elements are already sorted; bounding past them does redundant work and can also index out of bounds in some languages.
• Stability lost with <=. Swap on arr[j] > arr[j+1] is stable. Swap on arr[j] >= arr[j+1] swaps equal elements unnecessarily AND breaks stability.
• Forgetting the early exit. Without the swapped flag, your "optimized" bubble sort runs all n-1 passes even on a sorted input. The optimization is one variable; always include it.
• Trying to make it competitive. No matter how you optimize bubble sort — cocktail shaker sort, comb sort, etc. — it never beats O(n log n) sorts on real inputs. Don't fight the asymptote.