What is the complexity of bubble sort?

AlgorithmsJunior~2 min read

Short answer

Bubble sort has the following time complexity: O(n) in the best case (with an early-exit optimization), and O(n^2) in the average and worst cases. Its space complexity is O(1); the algorithm is stable and sorts in place.

Detailed breakdown

Time complexity

Best case: O(n), if a "were there any swaps" flag is used and the array is already sorted (the algorithm finishes after a single pass).
Average case: O(n^2) - arbitrary data requires roughly n·(n-1)/2 comparisons.
Worst case: O(n^2) - for a fully reverse-sorted array, the number of comparisons and swaps is maximal.

Space complexity

O(1) - the sort runs in place and needs only a constant amount of extra memory (loop variables and the swap flag).

Stability and adaptivity

Stable: equal elements keep their relative order.
Adaptive (with the optimization): if the array is nearly sorted, it finishes faster, down to O(n).

Number of comparisons and swaps

Comparisons in the worst (and average) case: n·(n-1)/2.
Swaps in the worst case: n·(n-1)/2; in the best case - 0 (if the early exit is used).
Without the early-exit flag, even a sorted array will still run ~n·(n-1)/2 comparisons.

Optimizations

The swapped flag: if no swaps happened during a pass - the array is sorted, so exit (gives the O(n) best case).
Shrinking the bound: after each pass the last element is in its final place - shrink the inner loop's length.
Remembering the last swap position: lets you shrink the next pass's range even further.
Bidirectional (cocktail) bubble sort: pushes large elements right and small ones left in a single cycle, speeding things up on some data.

When to use it, and when not to

Use it: for teaching purposes, very small arrays, nearly sorted data, when implementation simplicity and stability matter.
Don't use it: for medium and large arrays in production - there are O(n log n) algorithms that run faster (quicksort, mergesort, heapsort).

Example: optimized bubble sort (JavaScript, ES6)

function bubbleSort(arr) {
  const a = arr.slice(); // do not mutate the original array
  let n = a.length;
  let swapped;
  do {
    swapped = false;
    for (let i = 1; i < n; i++) {
      if (a[i - 1] > a[i]) {
        [a[i - 1], a[i]] = [a[i], a[i - 1]]; // swap
        swapped = true;
      }
    }
    n--; // the last element is already in place
  } while (swapped);
  return a;
}

console.log(bubbleSort([5, 1, 4, 2, 8])); // [1, 2, 4, 5, 8]

Example: bidirectional (cocktail) bubble sort

function cocktailSort(arr) {
  const a = arr.slice();
  let left = 0;
  let right = a.length - 1;
  let swapped = true;

  while (swapped) {
    swapped = false;
    // left-to-right pass
    for (let i = left; i < right; i++) {
      if (a[i] > a[i + 1]) {
        [a[i], a[i + 1]] = [a[i + 1], a[i]];
        swapped = true;
      }
    }
    right--;
    if (!swapped) break;

    swapped = false;
    // right-to-left pass
    for (let i = right; i > left; i--) {
      if (a[i - 1] > a[i]) {
        [a[i - 1], a[i]] = [a[i], a[i - 1]];
        swapped = true;
      }
    }
    left++;
  }
  return a;
}

console.log(cocktailSort([3, 0, 2, 5, -1, 4, 1])); // [-1, 0, 1, 2, 3, 4, 5]

Comparison with other algorithms

Insertion sort: also O(n^2), but usually faster than bubble sort in practice; best case O(n) with no extra memory, stable.
Selection sort: O(n^2), a minimal number of swaps (O(n)), but unstable; often faster than bubble sort in terms of memory writes.
Quicksort / Mergesort / Heapsort: asymptotically faster for large n - O(n log n), the preferred choice for production.

Short Answer

Interview ready

Premium

A concise answer to help you respond confidently on this topic during an interview.