Sorting Comparison —
O(n²) vs O(n log n), made visceral.
Every sort in this section produces the same sorted output — the difference is entirely in how much work it takes to get there, and that gap explodes as n grows. Run bubble sort and insertion sort on the same array on LearnBug and count the actual comparisons each one makes, side by side.
Why compare sorting algorithms at all?
They all produce identical output, so the choice between them is entirely about cost — time complexity, space complexity, and whether the sort is stable. Picking the wrong one doesn't cause a wrong answer; it causes a slow one, which only becomes visible at scale.
Why visualization helps
"O(n²) grows faster than O(n log n)" is easy to state and easy to underestimate. LearnBug can run two sorts on the exact same array and count real operations for each, so the growing gap between them is a number you watch increase, not just a formula you're told to trust.
Same output, very different cost
Bubble Sort
Repeated adjacent swaps, largest bubbles to the end each pass. Simple, but the most operations of the four for random input.
Insertion Sort
Shift-and-insert into a growing sorted prefix. Same O(n²) worst case as bubble sort, but far fewer operations on nearly-sorted data.
Merge Sort
Split, sort recursively, merge. Guaranteed O(n log n) in every case — the reliability trade-off is O(n) extra space.
Quick Sort
Pivot, partition, recurse. Usually the fastest in practice due to in-place partitioning — but a bad pivot choice degrades it to O(n²).
Counting real operations on [5, 1, 4, 2, 8]
Bubble sort on [5, 1, 4, 2, 8]: 10 comparisons total across all passes
4 comparisons in pass 1, 3 in pass 2, 2 in pass 3, 1 in pass 4 — 4+3+2+1 = 10, matching the formula n(n-1)/2 for n=5.
Insertion sort on the same array: only 6 comparisons — fewer, because of early exits
The inner while loop stops the moment it finds the right spot, instead of always scanning the whole remaining range like bubble sort's outer/inner loop structure does.
Merge sort on the same array: only 3 split levels, ~7 total comparisons — O(n log n) shape
log₂(5) ≈ 2.3, rounding up to 3 levels of splitting/merging — each level does at most n comparisons, so total work stays close to n × log n instead of n².
At n=5 the gap looks small — at n=10,000 it's the difference between instant and unusable
O(n²) at n=10,000 is 100,000,000 operations. O(n log n) at n=10,000 is about 133,000 operations — roughly 750× fewer. The gap barely matters for a 5-element array and completely dominates at real scale.
The lesson: Big O describes what happens as n grows, not what happens on a tiny example
Run two sorts on the same input
def bubble_sort(arr):
arr = arr[:]
n = len(arr)
for i in range(n - 1):
for j in range(n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
def insertion_sort(arr):
arr = arr[:]
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
data = [5, 1, 4, 2, 8]
print("Bubble:", bubble_sort(data))
print("Insertion:", insertion_sort(data))Complexity Comparison
Frequently asked questions
If merge sort and quick sort are both O(n log n), why does the choice still matter?
Big O hides constant factors — quick sort's in-place partitioning and better cache locality typically make it faster in practice for general array sorting, while merge sort's guarantee of never degrading to O(n²) and its stability make it the safer choice when those properties matter more than raw average-case speed.
Which sort should I actually use in real code?
In practice, you almost never hand-write any of these — Python's built-in sorted() and list.sort() use Timsort, a hybrid that combines merge sort's stability and worst-case guarantee with insertion sort's efficiency on small or nearly-sorted chunks. Understanding these four algorithms is about building intuition for complexity trade-offs, not picking one to implement by hand.
Why do bubble sort and insertion sort have the same Big O but different real speed?
Big O describes the growth rate, not the exact operation count — both are "on the order of n²," but insertion sort does meaningfully fewer actual comparisons and writes per element due to its early-exit behavior and shift-based placement. Two algorithms with identical Big O can still have very different constant factors.
Does the "best case" complexity ever matter in practice?
Yes, especially for insertion sort — if your data is frequently nearly-sorted (e.g. inserting new items into an already-sorted list, or re-sorting after a small change), insertion sort's O(n) best case can make it a genuinely better practical choice than an O(n log n) algorithm with more fixed overhead.
Run two sorts on the same array and count the difference
Paste any two sorting algorithms into LearnBug and compare their execution side by side.