Walkthrough — Module 20 (read after each stage is green)

Design commentary on reference/src/m20_networks.rs. This is the "compare with Knuth's answer" step: why the reference is shaped the way it is, the invariant that makes each piece correct, and the idioms worth stealing. You do not need any of this to pass — only to deepen.

Stage 1: Comparison lower bounds by decision trees

min_comparisons_lower_bound deliberately avoids f64::log2. Floating-point logs are treacherous exactly where we care most: lg 8! = lg 40320 ≈ 15.299, but near a true power of two a rounding error of 10⁻¹⁰ flips the ceiling. So the reference builds n! in a u128 and finds the least c with 2^c ≥ n! by shifting — pure integer arithmetic, exact by construction. This is the general lesson: when a value is defined by an integer inequality (smallest c with 2^c ≥ N), compute it with integers, never by rounding a float.

sort_and_count is a binary insertion sort, chosen because its comparison count is transparent and always at least the information bound's neighbourhood — it makes the "watch a real sort sit above ⌈lg n!⌉" demo honest. Note the count is data-independent (binary search always probes ⌈lg(i+1)⌉ positions), which is a nice contrast with Stage 2's data-dependent merge insertion.

Stage 2: Merge insertion (Ford–Johnson)

The one design decision that makes this tractable: sort indices, not values. mi_sort(idx, key, comps) orders the indices idx by key[idx]. Why? Because step M1 pairs elements and step M2 recursively sorts the larger of each pair — and after that recursion we must still know each larger element's smaller partner. If you recurse on bare values you lose the association; recursing on indices lets partner[hi] = lo survive, since indices are stable identities.

The invariant that makes M3 correct: the chain is always sorted, and b_i is known to be < a_i. So inserting b_i means binary-searching only the prefix of the chain before a_i's current position — never the whole thing. The reference finds that position with chain.iter().position(...); O(n) per insertion, but n ≤ 50 in the tests, so clarity wins over a fancier index map.

jacobsthal_order is where the optimality lives. It emits the 1-based indices 2..=maxi grouped by Jacobsthal numbers (1,3,5,11,21,…, generated by jcur += 2*jprev), each group from the top index down. The invariant it maintains — that when index i in group k is inserted, the searchable prefix has size 2^k − 1 — is what forces every binary search to cost exactly k with nothing wasted. Removing this ordering (inserting left to right) still sorts but blows the comparison budget; the reference's merge_insertion_meets_worst_ case_bound test would then fail because the exhaustive worst case would exceed F(n). The odd straggler is folded in as a phantom "highest index" with an unbounded search — Knuth's trick of treating the leftover as a b whose partner is +∞.

An idiom worth stealing: pass a &mut u64 counter down the recursion instead of returning counts and summing them. It keeps every comparison site a single *comps += 1 next to the actual <, so the count cannot drift from the code.

Stage 3: Sorting networks — Batcher's odd-even merge

The reference is a near-verbatim transcription of Batcher's recursion into a Vec<(usize,usize)>. The subtle line is the merge sweep, while i + r < lo + n { push((i, i+r)); i += m; } — this is the Python range(lo+r, lo+n-r, m) rewritten to avoid usize underflow (lo+n-r is fine here, but i + r < lo + n reads more safely). Getting the bounds wrong yields a network that is one comparator short and silently fails only on some inputs — which is exactly why Stage 3 pins the count (19 for n=8, 63 for n=16) as well as sortedness: the count is a cheap structural checksum.

apply_network is the whole point of obliviousness in three lines: it walks a fixed list and compare-exchanges. No branch decides which comparator comes next. Note comparators may list either wire first — apply_network always puts the min on the first-listed wire, so Stage 4's descending bitonic comparators (j, i) with j > i reuse the same primitive with zero special-casing.

network_depth computes the critical path with an ASAP schedule: each wire's ready layer is the earliest it is free, a comparator lands on max(ready[i], ready[j]), and both wires advance. Because the comparator list is already in a valid execution order, this single forward pass yields the true minimum depth — no need to build the dependency DAG explicitly. That it matches t(t+1)/2 is a non-trivial confirmation that the transcription is faithful.

Stage 4: The zero-one principle and bitonic sorting

sorts_all_zero_one is the constructive content of Theorem Z: it enumerates 2^n bitmasks (guarded by assert!(n < 32) so the 1u32 << n is safe) and checks each is sorted after the network runs. This is the 2^n certificate that replaces the n! brute force — the reason we can verify a 16-wire network at all. The dropping_a_comparator_breaks_it test exercises the converse value of the principle: a defective network is caught by some 0-1 counterexample, and the certificate finds it.

bitonic_sort_network mirrors the odd-even structure but carries a direction flag. The one idiom worth internalizing: a "descending comparator" is not a new kind of device — it is the same compare-exchange with its wires named in the other order, (i+m, i). Encoding direction in the tuple order rather than in apply_network keeps the applier dumb and universal, which is the whole spirit of oblivious sorting. The reference uses m = n/2 for the greatest power of two below n because n is constrained to a power of two — for general n you would take the greatest power of two strictly less than n, and the zero-one argument still goes through.