Sorting networks, fewest layers

# Sorting networks, fewest layers ## Goal A **sorting network** on `n` channels is a fixed sequence of comparators `(i, j)`, `i < j`: each puts the minimum of channels `i` and `j` on `i` and the maximum on `j`, and the network sorts if every input ends up non-decreasing along channels `0 .. n-1`. Comparators on disjoint channels can run in parallel; the **depth** is the number of layers when each comparator is scheduled as early as its two channels are free. The minimum depth `D(n)` (OEIS A067782) is known exactly for `n ≤ 17` (`D(17) = 10`); for `n = 18 .. 24` the best-known networks have depth 11 or 12 and the only proven lower bound is 10. Here you build networks for those seven `n` with as few layers as you can. `network.py` exposes network(n: int, time_budget: float, seed: int) -> list[tuple[int, int]] returning the comparators in order, each a pair `(i, j)` with `0 ≤ i < j < n`. Return the flat comparator list; the eval computes the layering itself (greedy: a comparator's layer is one more than the last layer that touched either of its channels), so the order you return determines the depth. The eval checks sortedness exactly with the **0-1 principle** (Knuth 5.3.4, Theorem Z): a network sorts all inputs iff it sorts all `2^n` inputs of zeros and ones, and all of them are run at once by holding each channel as a `2^n`-bit integer, so a comparator is one `&` and one `|` (2 MB integers at `n = 24`; still well under a second). A network that fails on any input fails the whole submission (the offending input is in the log). ## Metric The eval runs `network` on the fixed set `n = 18, 19, 20, 21, 22, 23, 24`, each with the given time budget (14 s by default), verifies the network, and reports metric = mean over n of record_depth(n) / depth(n) so 1.0 means matching every best-known depth and anything above 1.0 on an `n` is a new record (a depth-10 network on 18 or more channels would be a striking result). Per-instance detail (depth, size, record, lower bound, ratio, seconds) is in `per_instance`; any `n` you beat is listed under `records_beaten`, and the comparator list of every network is printed in the log. Size is reported for interest only: it does not enter the score, and the depth-optimal networks below are not the size-optimal ones (those live in the `sorting-network-size` pack). `ZT_EVAL_SEED` only changes the `seed` handed to your solver. ## Records Best-known depths and bounds from Bert Dobbelaere's "List of sorting networks" (https://bertdobbelaere.github.io/sorting_networks.html, summary table, page dated 2025-11-07, read 2026-09-07; its bounds column is OEIS A067782). The upper bounds are credited there to S. Al-Haj Baddar's 2009 thesis ("Baddar09", n = 18, 21, 22), Ehlers and Müller, "Faster sorting networks for 17, 19 and 20 inputs" (arXiv:1410.2736, "EM14", n = 19, 20) and T. Ehlers 2017 ("Ehlers17", n = 23, 24). The lower bound 10 for all of them follows from `D(17) = 10` (Codish, Cruz-Filipe, Ehlers, Müller, Schneider-Kamp, "Sorting networks: to the end and back again", 2016) because deleting a channel never increases depth. Every network behind these numbers was re-verified with the eval's own 0-1 check when this pack was written. **None of these depths is proven optimal.** | n | best-known depth | proven lower bound | size of that network | proven optimal | |---|---|---|---|---| | 18 | 11 | 10 | 78 | no | | 19 | 11 | 10 | 87 | no | | 20 | 11 | 10 | 93 | no | | 21 | 12 | 10 | 100 | no | | 22 | 12 | 10 | 107 | no | | 23 | 12 | 10 | 116 | no | | 24 | 12 | 10 | 122 | no | For comparison, Batcher's odd-even merge sort (the baseline) has depth 15 for every `n` in 17 .. 32. If you beat one, the comparator list is the evidence: it is in the eval log. Say so in your notes so the hub can update the table and forward the network to Dobbelaere's list. ## Iterating - Start on one or two sizes: `ZT_EVAL_INSTANCES=18,19 ZT_EVAL_PER_INSTANCE_SECONDS=2 python eval.py` runs in seconds. The full set takes about 100 s of solver time; verification is under a second per `n`. - Respect `time_budget` (seconds, per call). The eval kills the run if a call overruns it by more than 25% + 3 s. Be deterministic given `seed`: use `random.Random(seed)`. - Only the standard library is available (`math, random, itertools, functools, collections, heapq, time`). - The eval refuses networks with more than `3 · n(n-1)/2` comparators or more than three times the record's depth. - The baseline ships the bitmask 0-1 checker (`sorts(n, comps)`) and `depth(n, comps)`. Depth 12 for `n ≤ 24` is within reach by construction: sort two halves with known depth-optimal networks (depth 8 for 12 channels, 9 for 13–16) and merge them with an odd-even merge of depth `ceil(log2 n)`; the record holders got 11 by searching whole networks under a fixed depth. - How the records were found: Baddar and Ehlers–Müller fix the first one or two layers (a maximal matching in layer one, one of a few canonical second layers, both justified in Codish et al. 2016 / Bundala–Závodný 2014), then search the remaining layers with SAT or with a greedy "cover the most unsorted 0-1 inputs per layer" heuristic plus backtracking. Only the set of unsorted 0-1 vectors after the prefix matters, and it shrinks fast: after two good layers on 20 channels only a few thousand distinct vectors remain. - Reflection symmetry `(i, j) -> (n-1-j, n-1-i)` halves the search; Dobbelaere's networks are mostly symmetric. Deleting a channel from a good `n+1` network (drop every comparator touching it) keeps the depth, so a record for `n+1` is a record candidate for `n`. Write one honest line in `NOTES.md`: the idea, and which `n` it helped. Simpler is better: all else equal prefer the shorter solver. Log every experiment, including discards, in your results.tsv.