Bubble Sort Algorithm

The bubble sort algorithm is the simplest way to sort a list: walk through it, compare each pair of neighbours, and swap them when they are in the wrong order. Step through it yourself below, then read how it works, what it costs, and when (rarely) you should use it.

What is Bubble Sort?

Bubble Sort repeatedly steps through the list, compares each pair of adjacent elements and swaps them if they are in the wrong order. After each pass the largest remaining number has "bubbled" up to the end of the list, like a bubble rising to the surface.

Key insight: after pass k, the k largest numbers are already in their final positions, so every pass can stop one position earlier. If a whole pass makes no swap, the list is sorted and the algorithm can stop early.

A Worked Example

Here is bubble sort on the list [5, 1, 4, 2, 8], pass by pass:

Pass	Comparisons and swaps	List after the pass
1	5↔1 swap, 5↔4 swap, 5↔2 swap, 5 vs 8 no swap	[1, 4, 2, 5, 8]
2	1 vs 4 no swap, 4↔2 swap, 4 vs 5 no swap	[1, 2, 4, 5, 8]
3	1 vs 2 no swap, 2 vs 4 no swap — no swaps at all, so stop	[1, 2, 4, 5, 8]

Pass 1 moved 8 and 5 into their final places, and pass 2 placed 4. Pass 3 made no swaps, which proves the list is sorted, so the algorithm stops without running a fourth pass. That early exit is what gives bubble sort its O(n) best case.

Bubble Sort Time Complexity

Case	Time	Why
Best	O(n)	The list is already sorted: one pass with no swaps, then stop
Average	O(n²)	Elements need, on average, many passes to reach their place
Worst	O(n²)	A reverse-sorted list needs n(n−1)/2 comparisons and swaps
Space	O(1)	Sorts in place; only a temporary variable for swapping
Stable	Yes	Equal elements are never swapped, so their order is kept

To put the worst case in numbers: sorting 8 items in reverse order takes 28 comparisons, 1,000 items take 499,500, and 1 million items take roughly 500 billion. That quadratic growth is why bubble sort is never used for large inputs.

For a formal definition and complexity analysis, see the NIST Dictionary of Algorithms and Data Structures entry for bubble sort.

Algorithm Steps

1. Start at the first element.
2. Compare the current element with the next one.
3. If the current element is larger, swap them.
4. Move one position to the right and repeat until the end of the unsorted part.
5. The largest element of this pass is now in place, so shrink the unsorted part by one.
6. Repeat passes until a pass makes no swaps.

Advantages and Disadvantages

Advantages

• Very easy to understand and implement
• Sorts in place using O(1) extra memory
• Stable: equal elements keep their relative order
• Detects an already sorted list in O(n) with the early-exit check

Disadvantages

• O(n²) time makes it slow for large lists
• Performs many more swaps than Selection or Insertion Sort
• Rarely used in real systems

Real-World Applications

• Teaching sorting and algorithm analysis
• Very small lists where simplicity matters more than speed
• Checking whether a list is already sorted (one pass with no swaps)
• Tiny embedded or educational code where code size matters

When to Use Bubble Sort

Use it to learn how sorting works or for tiny, nearly sorted inputs. For anything larger, prefer Insertion Sort for small or nearly sorted lists, Merge Sort when you need guaranteed O(n log n) and stability, Quick Sort for fast in-memory sorting, or simply your language's built-in sort (Python and Java use Timsort).

Bubble Sort Implementation

Python

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:      # no swaps: already sorted
            break
    return arr

print(bubble_sort([5, 1, 4, 2, 8]))   # [1, 2, 4, 5, 8]

JavaScript

function bubbleSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    let swapped = false;
    for (let j = 0; j < n - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true;
      }
    }
    if (!swapped) break;   // no swaps: already sorted
  }
  return arr;
}

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

Both versions include the early-exit check: if an entire pass makes no swap, the loop breaks immediately.

FAQ

Is bubble sort stable?

Yes. It only swaps neighbours when the left one is strictly larger, so equal values never change places relative to each other.

Why is bubble sort O(n²)?

Each pass compares up to n−1 pairs, and in the worst case it needs about n passes. That nested loop gives roughly n²/2 comparisons, which grows quadratically.

What is the difference between bubble sort and insertion sort?

Both are O(n²), stable and in place. Bubble sort swaps neighbouring pairs across the whole unsorted part on every pass; insertion sort takes the next element and shifts it left into place. Insertion sort usually does less work in practice, especially on nearly sorted data.

Can bubble sort be faster than O(n²)?

Only in the best case. With the early-exit check, an already sorted list is confirmed in a single O(n) pass. Without that check, bubble sort always runs every pass.

---

More Sorting Algorithms

• Selection Sort — the other classic O(n²) sort, with fewer swaps
• Insertion Sort — the best simple sort for nearly sorted data
• Merge Sort — guaranteed O(n log n) with divide and conquer
• Quick Sort — the fast average-case workhorse