Bubble Sort repeatedly walks an array, swapping adjacent out-of-order pairs until the whole thing is sorted. Each pass “bubbles” the largest remaining value to the end.

Think of a line of concertgoers where you can only swap two neighbors at a time. Walk left to right, swapping every pair that is out of order. The heaviest person bubbles to the end after each pass — hence the name.

How It Works

1. Start at index 0 and walk to the end of the current unsorted region.
2. Compare each pair of adjacent elements arr[j] and arr[j+1].
3. If arr[j] > arr[j+1], swap them so the larger value shifts right.
4. After a full pass, the largest value has settled at the end — mark that position as sorted.
5. Repeat, shrinking the unsorted region by one each time, until a pass completes with zero swaps (the array is already sorted).

Key Insight

The early exit is the key insight. If a full pass makes no swaps, every adjacent pair is already in order — the entire array is sorted. This adaptivity gives Bubble Sort its O(n) best case, a rare property among naive sorts.

The trade-off: far more comparisons than necessary on large, random arrays. That is why Insertion Sort beats it in almost every practical scenario.

Worked Example

Sort [5, 3, 8, 1, 2] with Bubble Sort:

Pass 1 (compare/swap from left to right):

• 5 vs 3 → swap → [3, 5, 8, 1, 2]
• 5 vs 8 → keep → [3, 5, 8, 1, 2]
• 8 vs 1 → swap → [3, 5, 1, 8, 2]
• 8 vs 2 → swap → [3, 5, 1, 2, 8] — 8 is now home

Pass 2 (ignore the last position):

• 3 vs 5 → keep → [3, 5, 1, 2, 8]
• 5 vs 1 → swap → [3, 1, 5, 2, 8]
• 5 vs 2 → swap → [3, 1, 2, 5, 8] — 5 is now home

Pass 3:

• 3 vs 1 → swap → [1, 3, 2, 5, 8]
• 3 vs 2 → swap → [1, 2, 3, 5, 8] — 3 is now home

Pass 4:

• 1 vs 2 → keep → [1, 2, 3, 5, 8] — no swaps, early exit

Result: [1, 2, 3, 5, 8]. Watch the animation above — each pass colors the newly settled element, and the comparisons stop early because pass 4 makes zero swaps.

Edge Cases & Pitfalls

• Already sorted input — one pass detects zero swaps and terminates in O(n).
• Reverse sorted input — the worst case: every pass performs the maximum number of swaps, O(n²).
• Duplicates — Bubble Sort is stable: equal values never cross, since we only swap on strict >. This matters when sorting by multiple keys (e.g., price, then name).
• Large datasets — avoid Bubble Sort for production data. It degrades quadratically and performs far more comparisons than needed.

Comparison With Other Sorts

Insertion Sort dominates in practice: same complexity, fewer comparisons and swaps, and better cache behavior. Bubble Sort’s real value today is pedagogical.

Applications

• Teaching the mechanics of comparison-based sorting and stability
• Detecting a nearly sorted array cheaply (the early-exit pass)
• Very small datasets where simplicity outweighs speed

Practice Trajectory

1. Hand-trace Bubble Sort on [4, 2, 7, 1, 3], writing the array after every swap.
2. Add the swapped-flag optimization and explain why it turns the best case into O(n).
3. Prove that after pass k, the largest k elements are in their final positions.
4. Trace a run with duplicates ([3, 1, 3, 2]) and confirm the relative order of the two 3s is preserved.
5. Implement Bubble Sort iteratively, then explain why the naive version always takes n-1 passes even when the array is already sorted.