Empirical analysis lab: insertion sort
A counter in the wrong place quietly lies. First watch every key comparison get counted on a tiny array, then run the real experiment: hundreds of random arrays, a scatter plot, a fitted c·n² model, and a prediction for n = 10,000 that you check afterwards. Based on Levitin Exercises 2.6.1–2.6.2 (§2.6, empirical analysis of algorithms).
Part 1 · Where does the counter go?
Part 2 · The experiment
"20 random arrays" with 18 sizes is read as 20 arrays per size (360 runs), like the Java version in the repo. Each run sorts one copy with the counters and times a separate, uninstrumented copy (best of 2) with performance.now(). The work runs in small chunks so the page stays responsive.
Key comparisons C(n) · corrected counter
Every dot is one run. Lines: the least-squares fit c·n² and the hypothesis n²/4.
Key comparisons · given (buggy) counter
Same arrays, counter inside the loop body. On random input the bug hides: it misses only about n comparisons per array.
Running time (milliseconds)
Same shape, more noise: time depends on the machine, the browser and whatever else is running.
Ratio test: C(n) / n²
If C(n) ∈ Θ(n²), this ratio levels off at a constant. Which one?
Results and the n = 10,000 prediction
How to read this
- Part 1: the bars are the array. The yellow bar is A[j], being compared with the value v that is being inserted (shown top-left). Red bars were just shifted one place right. Both counters run at once, so you can see exactly which comparisons the given code forgets: the one false test that ends each insertion (unless j ran off the left end, where
andshort-circuits and no comparison happens at all). - Part 2, scatter plots: one dot per array, x = size n, y = the measured quantity. The vertical spread at each n is real run-to-run variation, not an error.
- Fit c·n²: least squares through the origin, c = Σ C·n² / Σ n⁴ over all runs.
- Hypothesis n²/4: for a random permutation the expected count is n(n−1)/4 + (n − 1) − (Hₙ − 1), where Hₙ = 1 + 1/2 + … + 1/n. Its leading term is n²/4.
Try this
- Part 1: load Sorted. The corrected counter says n − 1; the given counter says 0. That is the whole bug in one example.
- Part 1: load Reversed. Both counters agree on n(n−1)/2: every insertion runs off the left end, so there is never a false comparison to miss.
- Part 2: run the default experiment. The fitted c should land within about 1% of 0.25, and the ratio plot should flatten near 0.25.
- Before pressing "Measure n = 10,000", type your prediction. Theory says about 25,007,490. How close is the mean of 5 arrays? (The standard deviation of one array's count is about 167,000, so expect a wobble of tens of thousands.)
- Switch the input to already sorted with the buggy counter shown: the corrected plot is a straight line (n − 1), the buggy plot is flat at 0. Then try nearly sorted: fast, and nowhere near n²/4.