Smallest and fastest sorting networks
For each number of inputs n, how few comparators, and how few layers, can a comparator network have that sorts every input of n values?
Summary
A comparator network is a fixed list of compare-and-swap steps on n wires. The smallest possible number of comparators S(n) and layers D(n) of a network that sorts every input is known only for small n; for larger n only bounds are known. B. Dobbelaere keeps a list of the smallest and fastest networks known, with lower bounds and sources.
Source
Open, as listed by B. Dobbelaere, list of sorting networks · Smallest and fastest sorting networks. Checked 19 Nov 2026.
The status is the source’s. Papex does not decide whether a problem is solved.
Records on this problem
No public record addresses this problem yet.