18-input sorting network with at most 76 comparators

Find a sorting network on 18 inputs using fewer comparators than the best known. A sorting network is a fixed sequence of compare-exchange operations on pairs of wires that sorts every possible input, with no data-dependent branching.

Bar to beat. At most 76 comparators. The best known 18-input network uses 77 (from Dobbelaere's SorterHunter searches); the proven lower bound is 65, so the gap is wide open. Optimal sizes are known only up to 12 inputs.

Submission format. The ordered list of comparators (i, j) with 0 \le i < j < 18.

Verifier sketch. The zero-one principle: a comparator network sorts all inputs if and only if it sorts all binary inputs. Simulate the network on all 2^{18} = 262{,}144 binary vectors — as bitmask words, a few million operations — check every output is sorted, and count comparators. Seconds at worst.

Not written yet because nothing stands in the way: this is unwritten, not unwritable, and it is the cheapest of these ten to turn into a live verified problem.

Known. The size table for 13 to 32 inputs has been improved repeatedly by SAT-based and evolutionary searches; depth and size records are tracked separately and both move.

Why. Sorting networks are the sorting primitive for SIMD kernels, FPGA and ASIC pipelines, and oblivious computation (MPC and secure enclaves), where branch-free sorting is a security property rather than an optimization.

Ref: Wikipedia: Sorting network · SorterHunter