Sorting networks on 13 inputs need 45 comparators
Version 2 / Oct 26, 2026 / CC BY 4.0
Abstract
Let be the least number of comparators in a sorting network on inputs (the Bose–Nelson problem). We prove , so Juillé's network is optimal and . We also prove for , where is the least worst-case number of comparators met by the two largest inputs in a network that delivers them to fixed outputs, and is an explicit function of Van Voorhis. This proves the twenty tabulated lower bounds on for , which rested on an inequality of Van Voorhis whose published proof is invalid, and raises each of them by one. Both proofs use computer searches. Harder's method for applies Van Voorhis's one-value argument to the set of - vectors that a prefix of a network produces; for we extend the method from the largest value to the two largest. A search over prefixes bounds the rest of each network by deleting the comparators that the two largest, or the two smallest, inputs meet in it; the costs of the remaining sets are bounded using and exact values computed with Harder's program. The search writes a certificate, which is checked by a separate verifier and by a kernel-checked proof in Lean 4.
References
- R. C. Bose and R. J. Nelson, A sorting problem , J. ACM 9 (1962), no. 2, 282--296, doi:10.1145/321119.321126 (https://doi.org/10.1145/321119.321126).DOI
- M. Codish, L. Cruz-Filipe, M. Frank, and P. Schneider-Kamp, Sorting nine inputs requires twenty-five comparisons , J. Comput. System Sci. 82 (2016), no. 3, 551--563, doi:10.1016/j.jcss.2015.11.014 (https://doi.org/10.1016/j.jcss.2015.11.014).DOI
- L. Cruz-Filipe and P. Schneider-Kamp, Optimizing a certified proof checker for a large-scale computer-generated proof , Intelligent Computer Mathematics (CICM 2015), Lecture Notes in Comput. Sci., vol. 9150, Springer, Cham, 2015, pp. 55--70, doi:10.1007/978-3-319-20615-8_4 (https://doi.org/10.1007/978-3-319-20615-8_4).DOI
- L. Cruz-Filipe, K. S. Larsen, and P. Schneider-Kamp, Formally proving size optimality of sorting networks , J. Automat. Reason. 59 (2017), 425--454, doi:10.1007/s10817-017-9405-9 (https://doi.org/10.1007/s10817-017-9405-9).DOI
- B. Dobbelaere, Smallest and fastest sorting networks for a given number of inputs , web page, https://bertdobbelaere.github.io/sorting_networks.html, consulted 2026-10-18 (history entry of 2025-04-21).link
- R. W. Floyd and D. E. Knuth, The Bose--Nelson sorting problem , A Survey of Combinatorial Theory (J. N. Srivastava et al., eds.), North-Holland, Amsterdam, 1973, pp. 163--172, doi:10.1016/B978-0-7204-2262-7.50020-X (https://doi.org/10.1016/B978-0-7204-2262-7.50020-X).DOI
- J. Harder, Certificate of the minimal size of 11-channel sorting networks , Zenodo, 2019, dataset, doi:10.5281/zenodo.4108365 (https://doi.org/10.5281/zenodo.4108365).DOI
- J. Harder, An answer to the Bose--Nelson sorting problem for 11 and 12 channels , arXiv:2012.04400v3 [cs.DS], 2022.arXiv
- J. Harder, Lower size bounds for sorting networks (sortnetopt), source code, 2020, https://github.com/jix/sortnetopt, commit 0b5d09c . Its release v1, archived as doi:10.5281/zenodo.4139152 (https://doi.org/10.5281/zenodo.4139152), predates that commit. Isabelle/HOL files: the checker lemma check_proof_get_bound_spec in checker/ verified/ Checker.thy , restated in Checker_Codegen.thy ; the size bound lower_size_bound in Sorting_Network_Bound.thy .DOI
- Q. Huangfu and J. A. J. Hall, Parallelizing the dual revised simplex method , Math. Program. Comput. 10 (2018), no. 1, 119--142, doi:10.1007/s12532-017-0130-5 (https://doi.org/10.1007/s12532-017-0130-5).DOI
Show all 23 referencesShow fewer references
- H. Juillé, Evolution of non-deterministic incremental algorithms as a new approach for search in state spaces , Proceedings of the Sixth International Conference on Genetic Algorithms (L. J. Eshelman, ed.), Morgan Kaufmann, San Francisco, 1995, pp. 351--358.
- D. E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching , 2nd ed., Addison-Wesley, Reading, MA, 1998.
- L. de Moura and S. Ullrich, The Lean 4 theorem prover and programming language , Automated Deduction -- CADE 28, Lecture Notes in Comput. Sci., vol. 12699, Springer, 2021, pp. 625--635, doi:10.1007/978-3-030-79876-5_37 (https://doi.org/10.1007/978-3-030-79876-5_37).DOI
- The mathlib Community, The Lean mathematical library , Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs (CPP 2020), ACM, 2020, pp. 367--381, doi:10.1145/3372885.3373824 (https://doi.org/10.1145/3372885.3373824).DOI
- Mericanii, Twenty tabulated lower bounds for sorting networks rest on an invalid proof: an audit of Van Voorhis (1972), and a partial repair , draft, August 2026, https://mericanii.com/work/s13/paper-correction.pdf, consulted 2026-10-18.link
- T. S. Tomar, , GitHub repository, , commit .
- T. S. Tomar, Certificate and verifier for ``Sorting networks on 13 inputs need 45 comparators'' , Zenodo, 2026, doi: (https://doi.org/\suppdoi).link
- T. S. Tomar, Programs and logs for ``Sorting networks on 13 inputs need at least 44 comparators'' , Zenodo, 2026, doi: (https://doi.org/\supptwodoi).link
- T. S. Tomar, A kernel-checked Lean proof that sorting networks on 13 inputs need 45 comparators , Zenodo, 2026, doi: (https://doi.org/\kerneldoi).link
- T. S. Tomar, Sorting networks on 13 inputs need at least 44 comparators , Zenodo, 2026, doi:10.5281/zenodo.23498528 (https://doi.org/10.5281/zenodo.23498528).DOI
- T. S. Tomar, Sorting networks on 14 inputs need 50 comparators , Zenodo, 2026, doi:10.5281/zenodo.23622888 (https://doi.org/10.5281/zenodo.23622888).DOI
- D. C. Van Voorhis, An improved lower bound for sorting networks , IEEE Trans. Comput. C-21 (1972), no. 6, 612--613, doi:10.1109/TC.1972.5009021 (https://doi.org/10.1109/TC.1972.5009021).DOI
- D. C. Van Voorhis, Toward a lower bound for sorting networks , Complexity of Computer Computations (R. E. Miller and J. W. Thatcher, eds.), Plenum Press, New York, 1972, pp. 119--129, doi:10.1007/978-1-4684-2001-2_12 (https://doi.org/10.1007/978-1-4684-2001-2_12).DOI
Version history
- v1 · 47 pagesSubmitted by Tejasvi Singh TomarInitial depositSupersededOct 26, 2026
- v2 · 41 pagesSubmitted by Tejasvi Singh TomarThis version matches version 5 on Zenodo (doi:10.5281/zenodo.24299103). The version previously posted here matches version 3 on Zenodo; since then, Zenodo version 4 revised the exposition. Zenodo versions 1 to 4 used the wrong pronoun for Jannis Harder; version 5 replaces each occurrence with Harder's name or rewords the sentence to avoid a pronoun. It also adds the missing credit to Harder wherever the paper uses Harder's method, programs or certificate. It now states the licences of the reused code and data. The results and their proofs are unchanged.CurrentNov 17, 2026