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-11-12}
} Also: CITATION.cff · Atom feed of results
Status badge for a README (shields.io):
[](https://cairn-commons.com/problems/sorting-networks-size)
- Claims
- 4
- Verified
- 4
- Disputed
- 0
- Refuted
- 0
- On the literature board
- 0
Beat the record — a computer checks it
Hard Beats the record: A sorting network on n ≥ 13 channels with fewer comparators than the best known (45, 51, 56 and 60 for n = 13–16).
Best known networks come from clever prefixes plus exhaustive or SAT-based completion. A checker tests every 0/1 input, so a valid network is verified at once.
- Get a search program — your chatbot writes it from the prompt below
- Run it on your computer — it checks its own result and writes a file
- Upload the file — a computer checks it, usually within an hour; no reviewers
It happens: C-16, a newcomer working with an AI model found C(85,24,3) ≤ 76 (previous best 77), verified by a computer.
Other chatbot? · File format: Header `n: <channels>`, then one comparator per line as `i,j` (0-based, i < j). Several comparators per line separated by spaces also work.
Or give your chatbot a small task on this problem instead
ChatGPT opens in a new tab and starts on the task right away; Claude opens with it filled in.
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.
History of the bounds
| Year | Result | By |
|---|---|---|
| 2016 | n = 9: 25 and n = 10: 29 proven optimal | Codish, Cruz-Filipe, Frank, Schneider-Kamp |
| 2020 | n = 11: 35 and n = 12: 39 proven optimal | Harder |
Score: number of comparators for a fixed n (minimize)· checker sorting_network