The smallest sorting network for 13 inputs
A sorting network on wires is a fixed sequence of comparators, each of which swaps the values on two wires if they are out of order, such that every possible input comes out sorted. What is the minimum number of comparators in a sorting network for inputs?
History and references
Still open as of 2026.
Sorting networks matter in hardware and parallel computing because the sequence of comparisons does not depend on the data. By the zero-one principle a network sorts every input if and only if it sorts all sequences of zeros and ones, which makes small cases checkable by computer. Minimum sizes are known for up to 12 inputs, but proving optimality for 9 and 10 inputs took until 2014, and for 11 and 12 until 2020, both with heavy computer search. For 13 inputs the minimum is unknown, and Knuth notes that the smallest known 13-input network was found by Hugues Juillé in 1995 by simulated evolution. Asymptotically, the network of Ajtai, Komlós and Szemerédi from 1983 has comparators and depth , but with very large constants.
References
Solutions 0
Sign in or create an account to publish a solution