Papex

Open problem · Computer science · Open

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.

More in Computing