The film
About 4:30, hosted by Rerun. It asks you one question and waits for your answer before it shows you. The guide's voice is not recorded yet, so for now the film plays with captions; the full words are also below.
Nothing loads until you press play.
The lab: the row of shells
Pick a sort, a kind of row and a size, and watch it sort with every comparison counted; then look for a shell by knocking along or by halving. In the film's measurements, a jumbled row of 1,024 took 260,740 comparisons by insertion and 8,952 by merging; halving found any shell among 65,536 in at most 17 knocks.
Everything is computed on your computer, in this page. Nothing is sent anywhere.
Everything the film says
Search and sorting: the cost of looking
Search and sorting: the cost of looking.
Looking things up and putting them in order are two of the commonest jobs a computer does. Tonight Rerun counts the cost, one knock at a time.
One shell at a time
Rerun is looking for one shell in a row of 65,536. The plain way is to knock on each in turn until he finds it.
On average that took 32,921 knocks, about half the row. If the shell is not there, he knocks on all 65,536.
Halve the beach
Now suppose the shells are in order, smallest to largest. Knock on the middle one. If it is too big, the shell must be in the left half; too small, the right. Half the beach is gone in one knock.
Keep halving. For 65,536 shells it takes at most 17 knocks, and about 15 on average.
Sixty-five thousand shells, in order. How many knocks at most? (the film pauses here)
Only if they are in order
Halving only works because the shells are in order. Try it on a jumbled row of the same size and it still stops within 17 knocks, but even in its best run it missed 65,515 of the 65,536 shells that are there.
Fewer knocks is no good if the answer is wrong. So first, the shells have to be put in order.
Sorting by insertion
The simplest way: pick up each shell in turn and slide it left past every bigger one, the way many people sort a hand of cards.
On a row that is already in order, that is 65,535 comparisons for 65,536 shells, one for each shell after the first. On a row in reverse order it is 2,147,450,880. On a jumbled row, about 1,074,190,182.
Sorting by merging
A better way: split the row in half, sort each half, then merge the two sorted halves by walking along both and always taking the smaller front shell.
Each half is sorted the same way, down to single shells. On jumbled rows of 65,536, that took about 965,755 comparisons on average. Insertion took more than a thousand times as many.
How the cost grows
Double the row and see what happens. Knocking along it doubles. Halving adds one knock. Insertion sort on a jumbled row about quadruples. Merge sort a little more than doubles.
On this computer, sorting 65,536 jumbled shells took 1,151 milliseconds by insertion and 7.34 by merging.
What the count leaves out
These are counts of comparisons, not times. A real computer also pays for moving things and for memory, and the built-in sort that comes with the JavaScript engine, which counts nothing, took 2.99 milliseconds on the same row and the same computer.
But the counts tell you which way it grows, and that matters more as the row gets longer.
Goodnight
Put the shells in order once, and then halve the beach every time you look.
Goodnight.
Sources
Every claim in the film, with where it comes from and what that source does not prove. The numbers about the model are computed from its weights, which you can load and check: facts.json.
Night School's counts of comparisons. media/school/search/facts.json, written by tools/school/fill_search.mjs from system/school/search.mjs: linear and binary search, insertion and merge sort with counters, on sizes 8 to 65,536 and seeds 1 to 10, with 134 closed-form checks, a binary-search-on-unsorted control and Node timings. https://github.com/HarperZ9/HarperZ9.github.io/tree/main/media/school/search
Used for: Every count in the film, the closed-form checks and the control.
Does not prove: Times on other machines or engines; counts are of comparisons only.
Knuth, The Art of Computer Programming, vol. 3, 2nd ed. (1998). Donald E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, 2nd edition, Addison-Wesley, 1998; sections 5.2.1 (insertion), 5.2.4 (merging), 6.2.1 (binary search).
Used for: The standard treatment of these algorithms and their costs.
Does not prove: The film's exact counts, which are measured here; the section text was not read for this film.
Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, 4th ed. (2022), chapter 2. MIT Press, 2022; 2.1 Insertion sort, 2.3 Designing algorithms (merge sort).
Used for: Insertion sort and merge sort as described.
Does not prove: The film's counts; the book uses its own cost model.
What this lesson leaves out
Counts of comparisons, not times; real costs also depend on moves, memory and the machine.
The timings in the film are one computer's, with counting switched on.
Every closed form the film uses was checked against the counters at every size; the textbook sections were checked only by their tables of contents.
Next, on the same beach: Dynamic programming (A27).