Sorting algorithms · Big-O complexity

Sorting Race

Bubble sort vs merge sort vs quick sort on the same shuffled array. Big-O made visible.

Three sorting algorithms run on the same starting array. Bubble sort makes ~n² comparisons; merge and quick sort make ~n log n. With 30 elements that's a 6× gap. With 1,000 it's 100×. With 1,000,000 it's 50,000×. This is what complexity classes actually mean — not a textbook abstraction, but elapsed time you can watch.

30 elements, identical starting array, three algorithms.

Comparisons + writes count every operation. Watch the gap between the two columns on the right and the one on the left.

Bubble Sort

O(n²)

comparisons

writes

Merge Sort

O(n log n)

comparisons

writes

Quick Sort

O(n log n) avg

comparisons

writes

What you’re seeing: all three columns started with the same shuffled array. Bubble sort runs ~n² comparisons; merge and quick run ~n log n. With n=30, that’s ~900 vs ~150 — a 6× gap. With n=1,000, the gap is 100×. With n=1,000,000, it’s 50,000×. This is what Big-O complexity means in operational time.

What’s happening under the hood

›Bubble sort: O(n²) — compares every pair across n-1 passes. Worst case is also its average case. Used here because it makes the cost of bad complexity visible, not because anyone ships it.
›Merge sort: O(n log n) — divide the array in halves recursively, merge sorted halves. Worst case equals average case. Stable, predictable, the default for guaranteed bounds.
›Quick sort: O(n log n) average, O(n²) worst — partition around a pivot, recurse on each side. Faster than merge in practice because it sorts in place; the worst case is rare with good pivot selection.

Dig deeper

Phase 3 · Complexity and Big O

The concept you just explored is taught with full depth in the formal DURA curriculum.