Bubble Sort
Bubble sort repeatedly steps through the array, compares adjacent elements, and swaps them if out of order. Larger elements gradually "bubble up" to their correct positions at the end — like air bubbles rising through water.
💡 The Core Idea
Look at each adjacent pair (arr[j], arr[j+1]). If left > right, swap them.
After one full left-to-right pass, the largest unsorted element reaches its final position.
The last i elements are already sorted. Each pass works on a smaller range.
All Cases — Step by Step
😰 Worst Case — Reversed Array
Worst case: Reversed array [5, 4, 3, 2, 1]
When the array is in descending order, every comparison results in a swap. Each pass does the maximum possible swaps.
🚀 Best Case — Already Sorted
Best case: Already sorted [1, 2, 3, 4, 5]
When the array is already sorted, every comparison confirms elements are in order — no swaps needed at all.
⚡ Average Case — Nearly Sorted
Nearly sorted: [1, 2, 4, 3, 5] — one swap needed
Nearly sorted arrays are where bubble sort actually performs reasonably. Only the pair (4,3) is out of order.
🟰 Edge Case — All Equal
All equal elements: [3, 3, 3, 3, 3]
When all elements are the same, no swap is ever needed. Bubble sort uses strict > (not ≥) so equal elements are never swapped — preserving stability.
Stability Explained
Bubble sort is stable — equal elements never swap past each other. Try the demo:
Click 'Sort by Grade' to see bubble sort's stable behaviour — equal grades keep their original order.
The Critical Optimization — Early Exit
❌ Naïve Version
Always runs exactly n−1 passes, even on a sorted array. Completely unnecessary work.
for j in range(n-1-i):
if arr[j] > arr[j+1]:
swap(arr, j, j+1)
# Always O(n²) — even if sorted!
✅ Optimized Version
Tracks whether any swap occurred. If not → array is sorted → break early.
swapped = False
for j in range(n-1-i):
if arr[j] > arr[j+1]:
swap(arr, j, j+1)
swapped = True
if not swapped: break
Complexity Deep Dive
| Case | Input | Comparisons | Swaps | Time | Why |
|---|---|---|---|---|---|
| 😰 Worst | Reversed | n(n−1)/2 | n(n−1)/2 | O(n²) | Every pair is swapped every pass |
| 📊 Average | Random | n(n−1)/2 | n(n−1)/4 | O(n²) | Half the pairs need swapping on average |
| 🚀 Best | Already sorted | n−1 | 0 | O(n) | One pass detects 0 swaps → early exit |
| 🟰 Equal | All equal | n−1 | 0 | O(n) | No swaps in first pass → early exit |
| — | Space (all cases) | — | — | O(1) | In-place — no extra array needed |
Implementation
def bubble_sort(arr):
n = len(arr)
for i in range(n - 1): # n-1 passes
swapped = False
for j in range(n - 1 - i): # shrink window each pass
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
if not swapped: # early exit optimization
break
return arr
# Test all cases
print(bubble_sort([64, 34, 25, 12])) # Random → [12, 25, 34, 64]
print(bubble_sort([1, 2, 3, 4])) # Sorted → [1, 2, 3, 4] (O(n)!)
print(bubble_sort([4, 3, 2, 1])) # Reversed → [1, 2, 3, 4] (O(n²))
print(bubble_sort([])) # Empty → []function bubbleSort(arr: number[]): number[] {
const n = arr.length;
for (let i = 0; i < n - 1; i++) { // n-1 passes
let swapped = false;
for (let j = 0; j < n - 1 - i; j++) { // shrink window
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; // destructure swap
swapped = true;
}
}
if (!swapped) break; // 🚀 early exit — already sorted
}
return arr;
}
// Edge cases
bubbleSort([]); // [] — empty array, 0 iterations
bubbleSort([42]); // [42] — single element, already sorted
bubbleSort([3, 3, 3]); // [3,3,3] — equal, 0 swaps, O(n)
bubbleSort([5,4,3,2,1]); // reversed — O(n²) swapsEdge Cases to Handle
Empty array []
O(1)n=0, outer loop never runs. Return immediately. O(1).
Single element [x]
O(1)n=1, n−1=0 passes. Nothing to compare. Already sorted.
Two elements [a, b]
O(1)One comparison, at most one swap. Simplest non-trivial case.
All equal [x, x, x]
O(n)Zero swaps → early exit after 1 pass. Stable: order preserved.
Already sorted
O(n) optWith optimization: O(n). Without: O(n²) pointless passes.
Reversed array
O(n²)Worst case: O(n²) comparisons AND swaps. Every pair is wrong.
When to Use (and Not Use)
✅ Good for
- • Teaching — simplest sorting algorithm to understand and implement
- • Nearly sorted data — close to O(n) with optimization
- • Tiny arrays (n < 10) — overhead of complex sorts isn't worth it
- • Detecting if sorted — single-pass check is O(n)
- • Stability required + tiny data — simple stable sort
❌ Avoid when
- • Large datasets — O(n²) is catastrophic at n=100,000+
- • Performance matters — use Quick Sort or Merge Sort instead
- • Random large data — average case is still O(n²)
- • Production code — Tim Sort (Python/Java built-in) is always better
- • Worst-case guarantees needed — Heap Sort or Merge Sort are safer
Bubble Sort vs Others
| Algorithm | Best | Average | Worst | Space | Stable | Notes |
|---|---|---|---|---|---|---|
| 🫧 Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | ✅ | Simple; good for nearly sorted |
| 🃏 Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | ✅ | Faster than bubble in practice |
| 🎯 Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | ❌ | Fewest swaps; no early exit |
| 🔀 Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | ✅ | Best stable sort for large n |
| ⚡ Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | ❌ | Fastest in practice |
| 🐍 Tim Sort | O(n) | O(n log n) | O(n log n) | O(n) | ✅ | Python built-in; best all-rounder |
💡 Insertion Sort is almost always preferable to Bubble Sort — same complexity, but ~50% fewer comparisons on average because it stops early per element, not just per pass.