SorterHunter: An evolutionary approach to find small sorting networks (github.com)

SorterHunter is a new open-source C++ tool that uses evolutionary search to discover smaller and lower-latency sorting networks; its runs have already lowered the best-known comparator-count S(n) for many input sizes (notably n=18–29, 33–48 and 54–56) by 1–4 comparators versus prior bounds, and also reduced depth upper bounds (e.g., depth 14→13 for n=25,26; to 15 for n=34; and to 17 for n=42–44). The author published the program into the public domain and publishes curated tables (up to 64 inputs) of smallest/fastest networks, average/worst-case swap-optimized networks and median-selection networks, making these practical improvements and artifacts immediately available to the community. Technically, SorterHunter keeps both size (number of compare-exchange nodes) and depth low by tracking the Pareto front of (size,depth) pairs. It uses a fixed prefix strategy (empty, user-supplied, or a “greedy” prefix built by minimizing remaining 0–1 patterns) to massively reduce test vectors via the zero-one principle, and employs bit-parallel simulation (testing up to 64 binary vectors in parallel on a 64-bit machine) for speed. Candidate networks evolve via six mutation operators (removal, swaps, replacements, I/O line crossings, neighbor swaps, single-connection changes) with occasional uphill moves to escape local minima; mutants are accepted only if they pass the reduced test set. The approach is straightforward to build/run and provides a concrete, reproducible baseline and inspiration for further automated search and hardware-aware optimization of sorting networks.