To a seven-year-old
Knows: that numbers come in order and that you can tidy up a row of cards; does not know what a step, a rule, or a computer program is.
Look at the row of cards on the right. I dealt them, and I dealt them badly. A five, then a two, then a nine. They are in a muddle.
Tidying them means one thing: the smallest card goes on the left, and each card after it is a bit bigger, all the way to the biggest on the right. That's all. Like children lining up shortest to tallest.
Now, you can tidy them any way you like. Grab a card with your finger and drag it somewhere else. Drop the little 1 down at the front where it belongs. Tap a card first if you want to see its number get big.
The lazy way that always works
Here is my favourite rule, and it never fails. Look at all the untidy cards. Find the smallest one. Bring it to the front of the tidy part. Do it again.
That's the whole rule. Press find the smallest and watch: one card turns yellow — that's me looking at it — and then it slides into the green part of the row. The green part is the tidy part. It only ever grows.
Press it eight times and the whole row goes green. You never have to think. You just keep picking up the smallest card that's left.
Why tidy at all?
Because of finding. Press find the 6 while the row is still a muddle. My finger has to walk along and peek under every card, because the 6 could be hiding anywhere.
Now tidy the row and press it again. My finger goes straight to about the right place, because you already know a 6 lives near the big end. Tidy rows tell you where things are.
One more thing to watch. Down below there's a number: cards picked up. Every time I look at a card, it goes up by one. Try tidying by dragging, then shuffle and tidy with the button, and see which way makes that number bigger. Some ways of tidying are more work than others — and that, believe it or not, is what the rest of this page is about.
To a teenager
Knows: loops and if-statements, that programs can be fast or slow; does not know asymptotic notation or why a doubled input might quadruple the time.
Last level a child "picked up cards." Let's name what that actually was. Every tidy-up is made of exactly two kinds of move, and you can count them separately:
A comparison — you hold two cards and ask "is this one smaller?" In code that's one if (a[i] < a[j]). A move — you actually change where a card sits: a swap, or a shift one place right. Comparisons are cheap questions. Moves are work. A good algorithm is stingy with both, and different algorithms are stingy in different ways.
Selection sort: find the smallest, swap it forward
Scan the whole unsorted part for the smallest card, exchange it with the first unsorted slot, and repeat. That's the child's rule written down, and it's a real algorithm with a real name.
// selection sort for (i = 0; i < n; i++) { min = i; for (j = i+1; j < n; j++) if (a[j] < a[min]) min = j; // a comparison swap(a, i, min); // one exchange, always }
Count the inner loop: 7 comparisons, then 6, then 5… For eight cards that's 28, every single time. Selection sort does about n²/2 comparisons and exactly n exchanges, no matter what order you deal the hand. Hand it a hand that's already sorted and it still asks all 28 questions. It is beautifully, stupidly consistent.
Insertion sort: the bridge-hand method
This is how people actually sort cards. Take the next card. Slide the bigger cards already in your hand one place right to open a gap, and drop it in.
// insertion sort for (i = 1; i < n; i++) { v = a[i]; j = i; while (j > 0 && a[j-1] > v) { // compare a[j] = a[j-1]; j--; // shift right = a move } a[j] = v; }
Now the input order matters enormously. On an already-sorted hand the while test fails immediately every time: 7 comparisons, zero shifts. On a reversed hand every card must travel the whole way home: about n²/2 of each. Random order lands in between, around n²/4. Same code, three wildly different bills — that sensitivity has a name, adaptive, and it's why real library sorts hand short or nearly-ordered stretches to insertion sort.
Then: finding the 6
Sweeping the row left to right can cost all eight looks. But if the row is sorted, probe the middle instead: 6 is bigger than the middle card, so throw away the whole left half — four cards ruled out by one comparison. Halve, halve, halve: eight cards need at most three probes. Doubling the hand adds one probe, not eight looks.
In the panel, pick an algorithm and an input order and press step. Yellow means being compared, red means moved, green is the finished region. Watch the two counters. Then press race and read the tally: that gap between 28 and 7 is the entire subject in miniature.
| run | input | compares | moves |
|---|
To a computer science undergraduate
Knows: arrays, recursion, loop invariants, logarithms; does not know how to state O/Θ/Ω formally or solve a divide-and-conquer recurrence.
Level 2 handed you two tallies: 28 compares here, 9 there. Tallies are measurements of one input at one size. What you want is a function — cost as a function of n — and a language for comparing such functions that ignores what you cannot control (the machine, the compiler, the units) and keeps what you can (the shape of growth).
The three notations, stated properly
They are not synonyms for "fast", "slow" and "medium". Each is an existential claim about constants.
// upper bound f(n) = O(g(n)) iff ∃C>0, n₀ : 0 ≤ f(n) ≤ C·g(n) ∀ n ≥ n₀ // lower bound f(n) = Ω(g(n)) iff ∃C>0, n₀ : 0 ≤ C·g(n) ≤ f(n) ∀ n ≥ n₀ // tight: both at once f(n) = Θ(g(n)) iff ∃C₁,C₂,n₀ : 0 ≤ C₂·g(n) ≤ f(n) ≤ C₁·g(n)
O is an upper bound on the order of growth, witnessed by a constant C and a threshold n₀ 1; Ω flips the inequality to give a lower bound 1; Θ holds exactly when f is both O(g) and Ω(g) 1, which is the same as the sandwich 0 ≤ C₂g(n) ≤ f(n) ≤ C₁g(n) for n ≥ n₀ 1. Note what is quantified: the constants come after g is fixed, so "insertion sort is O(n²)" says nothing false about a sorted input — it is merely loose there.
Best, average, worst are three different functions
Fix the algorithm, and cost still depends on the input. For randomly ordered arrays of length N with distinct keys, insertion sort uses ~N²/4 compares and ~N²/4 exchanges on average; the worst case is ~N²/2 and ~N²/2, and the best case is N−1 compares and 0 exchanges 2. So insertion sort is Θ(n) on a sorted hand and Θ(n²) on a reversed one — and more generally O(kn) when no element is more than k places from home 3. Selection sort has no such luck: ~n²/2 compares and n exchanges, whatever the order 2. Switch the input dropdown in the panel and watch the compare counter for selection sort refuse to move.
Unrolling the recurrence
Divide and conquer gives recurrences of the form T(n) = a·T(n/b) + f(n), with a subproblems each of size n/b 45. Merge sort's merge step is Θ(n), so
T(n) = T(⌈n/2⌉) + T(⌊n/2⌋) + Θ(n), T(1) = Θ(1)
which is a = 2, b = 2, f(n) = Θ(n) 4. Draw the recursion tree: level i has 2i nodes of size n/2i, so each level costs n. The recursion bottoms out when n/2k = 1, i.e. k = log₂n, giving T(n) = n·T(1) + n log₂n = n log₂n + n = Θ(n log n) 4. Toggle the tree in the panel: every level's annotation reads Θ(n), and the depth is the log.
Quicksort partitions instead of merging — in place, O(log n) stack — but its worst case is Θ(n²) when pivots are terrible; heapsort is Θ(n log n) in place yet unstable; counting sort performs no comparisons at all, so its Θ(n+k) is not a contradiction of any comparison lower bound. Watch the stability lamp with the two fives: 5♠ dealt before 5♦ should still precede it. Insertion and merge keep them; selection, quick and heap need not 3.
To a PhD student in algorithms
Knows: recurrences, the Master Theorem, amortized analysis, the RAM model; does not have a feel for how badly the RAM model's constants mispredict a real machine.
You can already solve the recurrence. T(n) = aT(n/b) + f(n), with a the number of subproblems and b the factor by which the subproblem size shrinks 54, and the Master Theorem hands you an asymptotically tight bound whenever the split is into subproblems of equal size 5. Merge sort is a=2, b=2, f=Θ(n) and out comes Θ(n log n). Worth knowing whose theorem it is: Bentley, Blostein and Saxe presented the unifying method in 1980; the name "master theorem" was popularised by CLRS 5.
So the theory is settled and this level is short? No. This level is where the claim gets tested. The panel to your right is not an animation. It generates arrays in the browser, sorts them, and times them with the clock your laptop actually has. Push the max n slider right and points accumulate; a least-squares line through the log-time-versus-log-n cloud gives you a fitted exponent. Watch it settle. Merge sort will not converge to 1.00, because n log n is not a power law — you should see something drifting around 1.05–1.15 over this range, and the drift itself is the log factor showing up as curvature. Insertion sort on random data will march toward 2. If your fit says 1.6, you have not discovered a new algorithm; you have too few points, too little repetition, or a garbage-collection spike in the middle of your window.
The parenthesis that eats your prediction
Asymptotic optimality is defined "in an asymptotic sense, ignoring constant factors" 6. That clause is load-bearing. Its own literature says so plainly: because such algorithms are only optimal asymptotically, "further machine-specific tuning may be required to obtain nearly optimal performance in an absolute sense" 6. Below the crossover the constant is the whole story. Drag the hybrid cutoff slider: at cutoff 1 you have pure merge sort; push it to 30–60 and total time drops, because insertion sort is adaptive — O(kn) when no element is more than k places from home — and also stable, in-place and online 3. That is not a hack, it is why every production hybrid you have read about switches to insertion sort on short runs.
Hardware arrives as a constant on the leading term
Quicksort's real cost is not "Θ(n log n) full stop". Write it the way the analysis does: T_n = (1 + β(s,p))·H(s,p)·n ln n + O(n) 7. The misprediction-dependent factor β multiplies the leading term. It does not change the exponent, so your log-log fit will not see it — and it can change the wall-clock by a large factor. Where does β come from? The branch predictor "keeps records of whether or not branches are taken", so after a branch has been seen several times it predicts from that record 8. A presorted input makes the comparison branch trivially predictable; a random input makes it a coin flip. Same comparison count, different time.
That is the experiment to run, and the panel runs it: flip the readout to compares, note the count on sorted versus random input for merge sort, then flip to milliseconds and compare again. The counts barely move; the clock does.
The honest limits of this panel: JavaScript timer resolution is coarsened in browsers, the JIT warms up during your first repetition, and you are sharing a core with everything else you have open. So treat the fitted exponent as a hypothesis test on the shape — 1-ish, log-ish, or quadratic — and treat any two-algorithm comparison within 20% as a tie. What survives all of that is the structural claim: exponents come from recurrences, and everything below the exponent comes from the machine.
To a peer — an algorithms researcher
Knows: decision trees, cache-oblivious analysis, the folklore around quicksort tuning; wants to argue about which model earns its keep.
Let me retract, politely, most of what level 4 implied. Level 4 said: fit the exponent, watch it converge, trust the curve. That is a fine undergraduate hygiene lesson and a bad research posture. The exponent converging to 1.08 tells you which model you are in, not which program to ship. Everything interesting about sorting in 2024 lives in the constant that the model throws away — and the parenthesis where it is thrown away is load-bearing: an optimal cache-oblivious algorithm "uses the cache optimally (in an asymptotic sense, ignoring constant factors)" 6, and the same source concedes in the next breath that "further machine-specific tuning may be required to obtain nearly optimal performance in an absolute sense" 6.
The lower bound is geometry about a model
Take the left view in the panel. Drag n from 3 to 5 and watch the decision tree fan out. A comparison sort is a binary tree whose internal nodes are comparisons and whose leaves are the permutations it can distinguish; you need n! distinguishable leaves, a binary tree of height h has at most 2^h leaves, therefore h ≥ log₂(n!). At n=5 that is 120 leaves, height ≥ 6.9, so 7 comparisons — and the panel will show you an actual worst-case path of length 7.
This is a beautiful theorem and it constrains nothing physical. It says: any algorithm whose only access to the keys is a two-way comparison needs that many comparisons. Counting sort reads the keys as addresses and does zero comparisons, so its Θ(n+k) is not a violation but an escape 1. Nothing about the bound mentions the cost of a comparison — and on this machine, comparisons are not fungible.
The pivot heresy
Here is the result I would put in front of anyone who still says "take the median of the sample." Martínez and collaborators write quicksort's total cost as
// s = sample size, p = pivot rank fraction Tn = (1 + β(s,p)) · H(s,p) · n ln n + O(n)
where β is the misprediction-dependent factor and H the comparison factor 7. And then: "there exists a threshold value c such that if [β below] c (branch mispredictions are not too expensive) then we have to take the median of the samples, i.e., [p] = 1/2 … If [β above] c (that can happen often in practice!) then [p] < 1/2" 7. Drag the misprediction-penalty slider in the middle view. Below the threshold the minimiser sits at 0.5. Push past it and the optimum slides off centre — the folklore is a special case of a cost model nobody was using.
The why is the part I find genuinely disquieting, because it is not an accident of one CPU. "In comparison-based algorithms, we want comparisons to yield as much information as possible ⟹ difficult to predict!" 7. The information-theoretically best comparison is the coin flip; the coin flip is exactly what a branch predictor cannot learn. Modern pipelines punish that: mispredictions cost "between 10 and 20 clock cycles" 8, because the speculatively executed instructions "are discarded and the pipeline starts over with the correct branch" 8 — and the delay equals the pipeline depth from fetch to execute 87. Branch prediction is a first-order determinant of real performance 8, and the RAM model does not have a slot for it.
Two localities, one collapsed axis
Same complaint on the memory side. Cache-conscious code exploits temporal locality — refetching the same memory — and spatial locality — touching nearby addresses 6; these are independent axes, and the RAM model collapses both to "one unit." The ideal-cache model is tractable precisely because it ignores "complex associativity, replacement policies, etc.", and is only "provably within a constant factor of a more realistic cache's performance" 6. Within a constant factor. Which is the whole quantity in dispute.
What I will and will not claim
Switch the cost metric in the panel from compares only to compares + mispredictions and run the adversarial hands. On the median-of-three killer, quicksort's comparison count blows up toward n²/2; on all-duplicates with a naive partition it does too. That much is arithmetic. But notice what happens when you press the honesty toggle: half the chips turn grey. The pivot-skew result comes from a conference-talk PDF with mangled glyph extraction 7, the cache claims are Wikipedia-grade 6, and I have no evidence in this ledger about hash-flooding, adversarial-input attacks on hash tables, or the SIMD sorting networks that now beat all of this in libraries. The open questions I would actually supervise: what is the right analytic model that prices β and cache misses jointly without becoming unfalsifiable, and does the skewed-pivot optimum survive on today's much deeper pipelines and much better predictors? I do not know. Neither does the parenthesis.