Richards.AI
Library · Five LevelsHuman LearningSeptember 3, 2026

Sorting and Searchingexplained at five levels

One professor, one shuffled hand of eight numbered cards, five audiences. A child drags cards into order; a teenager counts the comparisons; an undergraduate drives the algorithms in notation; a PhD student fits a growth curve to live timings; a peer argues about branch mispredictions and skewed pivots.

The hand we will sort
Eight numbered cards dealt in the order 5, 2, 9, 1, 5♦, 6, 3, 8 — with two fives so stability shows, and a target value 6 to search for.
  1. 1A childage seven
  2. 2A teenagercurious, some code
  3. 3An undergradcomputer science
  4. 4A PhD studentalgorithms
  5. 5A peeralgorithms researcher
Interactive explainer · one tab per levelOpen standalone ↗

Preview

5 levels
Level 1 previewLevel 2 previewLevel 3 previewLevel 4 previewLevel 5 preview

Sources

8 sources
  1. 1.Big O vs Theta Θ vs Big Omega Ω Notations - GeeksforGeeksevidence sq2-5, sq2-6, sq2-7, sq2-8
  2. 2.Elementary Sortsevidence sq1-4, sq1-2
  3. 3.Insertion sort - Wikipediaevidence sq1-8
  4. 4.Solving Recurrencesevidence sq2-11, sq2-9, sq2-10
  5. 5.Master theorem (analysis of algorithms) - Wikipediaevidence sq2-4, sq2-3, sq2-2, sq2-1
  6. 6.Cache-oblivious algorithm - Wikipediaevidence sq3-5, sq3-6, sq3-7, sq3-8
  7. 7.Branch Mispredictions in Quicksortevidence sq3-4, sq3-3, sq3-2, sq3-1
  8. 8.Branch predictor - Wikipediaevidence sq3-11, sq3-9, sq3-10, sq3-12

Verification

20 claims

Every material claim in the prose was checked against the evidence ledger by an independent verifier pass: 4 partial, 16 supported.

ClaimVerdictNote
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 exchangessupportedsq1-4 states verbatim the average ~N²/4 compares/exchanges, worst ~N²/2, best N-1 compares and 0 exchanges.
Selection sort has no such luck: ~n²/2 compares and n exchanges, whatever the orderpartialsq1-2 gives ~n²/2 compares and n exchanges, but says nothing about being independent of input order ('whatever the order').
Insertion sort is more generally O(kn) when no element is more than k places from homesupportedsq1-8 states time complexity is O(kn) when each element is no more than k places from its sorted position.
Insertion sort is adaptive — O(kn) when no element is more than k places from home — and also stable, in-place and onlinesupportedsq1-8 lists adaptive with O(kn), stable, in-place, and online.
Insertion and merge sort keep ties in original order (stable); selection, quick and heap need notpartialsq1-8 supports insertion sort's stability only; nothing about merge sort's stability or the non-stability of selection, quick, and heap sort.
O is an upper bound on the order of growth, witnessed by a constant C and a threshold n₀supportedsq2-5 defines O as an upper bound on order of growth with positive constants C and n0.
Ω flips the inequality to give a lower boundsupportedsq2-6 defines Ω as a lower bound with the inequality 0 <= Cg(n) <= f(n).
Θ holds exactly when f is both O(g) and Ω(g) , which is the same as the sandwich 0 ≤ C₂g(n) ≤ f(n) ≤ C₁g(n) for n ≥ n₀supportedsq2-7 defines Θ as both O and Ω, and sq2-8 gives the sandwich inequality with C1, C2 for n >= n0.
Divide and conquer gives recurrences of the form T(n) = a·T(n/b) + f(n), with a subproblems each of size n/bsupportedsq2-11 gives the form T(n)=aT(n/b)+f(n) for divide-and-conquer and sq2-4 explains a as the number of subproblems and b as the size-reduction factor.
Merge sort's recurrence T(n) = T(⌈n/2⌉) + T(⌊n/2⌋) + Θ(n), T(1) = Θ(1) is a = 2, b = 2, f(n) = Θ(n)partialsq2-9 gives the recurrence with Θ(1) at n=1 and Θ(n) merge cost, but does not itself state the identification a=2, b=2, f(n)=Θ(n).
The recursion bottoms out when n/2^k = 1, i.e. k = log₂n, giving T(n) = n·T(1) + n log₂n = n log₂n + n = Θ(n log n)supportedsq2-10 states the recurrence becomes trivial when n/2^k=1, k=log2 n, T(n)=nT(1)+n log2 n = n log2 n + n, and Θ(n log n).
The Master Theorem hands you an asymptotically tight bound whenever the split is into subproblems of equal sizesupportedsq2-3 says the master theorem always yields asymptotically tight bounds for divide-and-conquer recurrences partitioning input into subproblems of equal sizes.
Bentley, Blostein and Saxe presented the unifying method in 1980; the name "master theorem" was popularised by CLRSsupportedsq2-2 credits Bentley, Blostein, Saxe (1980) with the 'unifying method' and CLRS with popularizing the name.
Asymptotic optimality is defined "in an asymptotic sense, ignoring constant factors"supportedsq3-5 uses exactly the phrase 'in an asymptotic sense, ignoring constant factors' for optimality.
Because such algorithms are only optimal asymptotically, "further machine-specific tuning may be required to obtain nearly optimal performance in an absolute sense"supportedsq3-6 contains the quoted sentence verbatim about further machine-specific tuning.
Quicksort's cost can be written as T_n = (1 + β(s,p))·H(s,p)·n ln n + O(n), where β is the misprediction-dependent factor and H the comparison factorpartialsq3-4 shows T_n = (1+β(s,p))H(s,p) n ln n + O(n), but the quote does not define β as misprediction-dependent or H as the comparison factor.
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 recordsupportedsq3-11 says the predictor keeps records of whether branches are taken and bases prediction on recorded history after seeing a jump several times.
Martínez et al. state: "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"supportedsq3-3 contains the threshold statement matching the paraphrased quote with symbols elided as bracketed β and p.
Mispredictions cost "between 10 and 20 clock cycles" , because the speculatively executed instructions "are discarded and the pipeline starts over with the correct branch" — and the delay equals the pipeline depth from fetch to executesupportedsq3-9 gives 10–20 cycles and the pipeline-depth equivalence, and sq3-10 gives the discard-and-restart mechanism.
The ideal-cache model ignores "complex associativity, replacement policies, etc.", and is only "provably within a constant factor of a more realistic cache's performance"supportedsq3-8 mentions complex associativity, replacement policies, and being provably within a constant factor of a more realistic cache.

How this was made

Researched by the Richards.AI deep research agent: the topic was scoped, decomposed into subquestions researched by parallel subagents into an append-only evidence ledger, written at five levels on one running example, audited by an independent claim-verification pass, and its interactive panels were exercised in a headless browser before publication.

Preset
quick
Reason lane
anthropic:claude-opus-5
Verifier lane
anthropic:claude-opus-5
Evidence records
32
Browser validation
passed
Prompt revision
4b9087b9e9c6 / 874deb875128