Quicksort Harmonic Analysis
E[comparisons] = 2n·H
n
≈ 2n·ln(n). P(i,j compare) = 2/(j−i+1). Harmonic numbers govern the average.
n=1000 expected
≈ 13,816
n=1000 worst case
499,500
Harmonic H₁₀₀₀
≈ 6.908
Pair(dist=1) P
1.000
Pair(dist=500) P
≈ 0.004
Pivot:
Random pivot
First element (worst case for sorted)
Sort n=50
Auto-Sort
Reset Array
Run 200 Trials (n=50)
n (theory curve):
200
P(i,j compare) = 2/(j−i+1) — Upper-Triangular Heatmap (n=100)
Dark red = P≈1 (adjacent pairs). Light = P≈0 (distant pairs). Flash on active comparisons.
Animated Sort (n=50)
Click "Sort n=50" to begin.
Comparison Curves (n = 10 to max-n)
2n·ln(n) (theory)
n²/2 (worst)
Running average
Regret / Trial Distribution (200 trials)
Run trials to see comparison distribution.