Sorting networks on 15 and 16 inputs need 55 and 60 comparators, and 20 inputs need 81

Let S(N) be the least number of comparators in a sorting network on N inputs. We prove that S(16) = 60, so the sorting network with 60 comparators that Green found in 1969 has the fewest possible comparators. We also prove that S(15) ≥ 55, which leaves 55 and 56 as the possible values of S(15), and that S(20) ≥ 81. Together, these results raise the previously known lower bounds on S(N) for 17 ≤ N ≤ 32 by two for even N ≥ 20 and by one otherwise. The lower bounds for 16 and 20 inputs come from a rigidity argument: in a sorting network with one comparator fewer than the bound to be proved, the lower bounds for fewer inputs, among them S(15) ≥ 55 at 16 inputs and S(16) ≥ 60 at 20 inputs, fix the comparators through which the two largest and the two smallest values pass, wherever they enter, up to an explicit list of choices, and a computation rules out each choice. At 20 inputs, fixing these comparators also needs a search over the ways in which the two largest values can pass through the network. The proof of S(15) ≥ 55 follows the method of our computer-assisted proof of S(14) ≥ 50 and adds new lower bounds of Huffman type on the number of comparators needed to sort a set of vectors. Separately written programs check the computations. In Lean 4 we prove one step of the argument for S(15) ≥ 55 and derive the three results, assuming only two tables of bounds from our proof of S(14) ≥ 50 that are certified outside Lean; some steps are evaluated by compiled code rather than by Lean's kernel. The certificates of the computations, the programs that produced and checked them, and the logs of their runs are archived as doi:10.5281/zenodo.24156536, and the Lean proofs as doi:10.5281/zenodo.24156534. Mathematics Subject Classification (2020): 68P10 (primary); 68Q06, 05C05, 68V05 (secondary).

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-12
DOI
https://doi.org/10.5281/zenodo.24156529
Primary Topic
Complexity and Algorithms in Graphs
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Sorting networks on 15 and 16 inputs need 55 and 60 comparators, and 20 inputs need 81

Tejasvi Singh Tomar
Zenodo (CERN European Organization for Nuclear Research)
Complexity and Algorithms in Graphs
preprint

Sorting networks on 15 and 16 inputs need 55 and 60 comparators, and 20 inputs need 81

Tejasvi Singh Tomar
preprint en

Abstract

Let S(N) be the least number of comparators in a sorting network on N inputs. We prove that S(16) = 60, so the sorting network with 60 comparators that Green found in 1969 has the fewest possible comparators. We also prove that S(15) ≥ 55, which leaves 55 and 56 as the possible values of S(15), and that S(20) ≥ 81. Together, these results raise the previously known lower bounds on S(N) for 17 ≤ N ≤ 32 by two for even N ≥ 20 and by one otherwise. The lower bounds for 16 and 20 inputs come from a rigidity argument: in a sorting network with one comparator fewer than the bound to be proved, the lower bounds for fewer inputs, among them S(15) ≥ 55 at 16 inputs and S(16) ≥ 60 at 20 inputs, fix the comparators through which the two largest and the two smallest values pass, wherever they enter, up to an explicit list of choices, and a computation rules out each choice. At 20 inputs, fixing these comparators also needs a search over the ways in which the two largest values can pass through the network. The proof of S(15) ≥ 55 follows the method of our computer-assisted proof of S(14) ≥ 50 and adds new lower bounds of Huffman type on the number of comparators needed to sort a set of vectors. Separately written programs check the computations. In Lean 4 we prove one step of the argument for S(15) ≥ 55 and derive the three results, assuming only two tables of bounds from our proof of S(14) ≥ 50 that are certified outside Lean; some steps are evaluated by compiled code rather than by Lean's kernel. The certificates of the computations, the programs that produced and checked them, and the logs of their runs are archived as doi:10.5281/zenodo.24156536, and the Lean proofs as doi:10.5281/zenodo.24156534. Mathematics Subject Classification (2020): 68P10 (primary); 68Q06, 05C05, 68V05 (secondary).

Zenodo (CERN European Organization for Nuclear Research)
Complexity and Algorithms in Graphs
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon