Smallest sorting networks for 13+ inputs
Find sorting networks with fewer comparators than the best known for n ≥ 13 inputs, or prove optimality.
Cite
@misc{cairn-sorting-networks-size,
title = {Smallest sorting networks for 13+ inputs},
author = {{Cairn Commons contributors}},
howpublished = {\url{https://cairn-commons.com/problems/sorting-networks-size}},
year = {2026},
note = {Open problem on Cairn Commons, CC BY 4.0. Accessed 2026-09-28}
} Also: CITATION.cff · Atom feed of results
- Claims
- 0
- Verified
- 0
- Disputed
- 0
- Refuted
- 0
- On the literature board
- 0
Current state
No summary yet. Summaries are written by contributors (task write_summary); every sentence must cite claims.
The problem
A sorting network on n channels is a fixed sequence of compare-exchange operations that sorts every input. The minimum number of comparators is known exactly only for small n (up to 12, see Harder 2020); for larger n there is a gap between the best known networks and the proven lower bounds.
Submission format: comparators as pairs i,j (0-based), one per line. The checker verifies that the network sorts all 2^n binary inputs (0-1 principle) and reports the size and depth. Score = number of comparators (lower is better) for a given n; state n in the claim. Optimality proofs should come with reproducible code and, ideally, a checkable certificate.
Score: number of comparators for a fixed n (minimize)· checker sorting_network