Sorting networks, fewest comparators

# Sorting networks, fewest comparators ## Goal A **sorting network** on `n` channels is a fixed sequence of comparators `(i, j)`, `i < j`: each comparator swaps the values on channels `i` and `j` if the one on `i` is larger, so afterwards channel `i` holds the minimum and channel `j` the maximum. The network *sorts* if every input ends up in non-decreasing order along channels `0 .. n-1`. The **size** is the number of comparators; the minimum size `S(n)` (OEIS A003075) is known exactly only for `n ≤ 12`. Here you build networks for `n = 13 .. 17` with as few comparators 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` (a comparator with `i > j` is rejected: the convention is that the minimum goes to the lower channel). 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 (bit `v` of channel `i` is the value channel `i` carries on input `v`), so a comparator is one `&` and one `|`. A network that fails on any input fails the whole submission (the offending input is in the log); a network that sorts scores by its size. ## Metric The eval runs `network` on the fixed set `n = 13, 14, 15, 16, 17`, each with the given time budget (20 s by default), verifies the network, and reports metric = mean over n of record_size(n) / size(n) so 1.0 means matching every best-known size and anything above 1.0 on an `n` is a new record. Per-instance detail (size, depth, 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. Depth (number of parallel layers) is reported for interest only: it does not enter the score, and the size-optimal networks below are not the depth-optimal ones (those live in the `sorting-network-depth` pack). `ZT_EVAL_SEED` only changes the `seed` handed to your solver. ## Records Best-known sizes and the current lower 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 A003075), which cites Knuth, *TAOCP* vol. 3 §5.3.4 for `n ≤ 16` and S. Al-Haj Baddar's 2009 thesis ("Baddar09") for the 17-channel upper bound. Every network behind these numbers was re-verified with the eval's own 0-1 check when this pack was written. **None of these sizes is proven optimal**: optimality is known for `n ≤ 8` (Floyd–Knuth), `n = 9, 10` (Codish, Cruz-Filipe, Frank, Schneider-Kamp 2016) and `n = 11, 12` (Harder 2021). The 45-comparator 13-channel network was found by Hugues Juillé (1995, END evolutionary search); the 60-comparator 16-channel network is Green's (1969). | n | best-known size | proven lower bound | depth of that network | proven optimal | |---|---|---|---|---| | 13 | 45 | 44 | 10 | no | | 14 | 51 | 48 | 10 | no | | 15 | 56 | 53 | 10 | no | | 16 | 60 | 57 | 10 | no | | 17 | 71 | 63 | 12 | no | For comparison, Batcher's odd-even merge sort (the baseline, after pruning comparators that never swap) uses 48, 53, 59, 63 and 79 comparators. 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=13,14 ZT_EVAL_PER_INSTANCE_SECONDS=2 python eval.py` runs in seconds. The full set takes about 100 s of solver time; verification is milliseconds. - 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 three times the record's comparators. - The baseline ships the bitmask 0-1 checker (`sorts(n, comps)`); the same integers give you a cheap fitness for search: after a prefix of comparators, the number of distinct channel-value patterns (or of unsorted 0-1 inputs) left is what the suffix still has to fix. - What the record holders did: Juillé's END and Valsalam–Miikkulainen (2013) evolved networks by fixing a good symmetric prefix (the first layers of a known network, or a maximal matching of channels) and searching the suffix; Dobbelaere's SorterHunter mutates a working network (swap, replace, insert, delete comparators), repairs it with a greedy completion, and keeps it when size does not grow, with reflection symmetry `(i, j) -> (n-1-j, n-1-i)` enforced to halve the search. Deleting a channel from a good `n+1` network (drop every comparator touching it) gives a valid `n` network: 56 for 15 and 51 for 14 come from the 16-channel network this way. - Knuth's exercises in 5.3.4 and the CCFS16 paper explain why the first layer can be taken as a maximal matching and the second as one of a few canonical forms; that prunes an enormous amount. - Local moves that keep a network sorting: a comparator is redundant if the network still sorts without it; two comparators on disjoint channels commute; a comparator `(i, j)` can be moved across another if they share no channel. 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.