Sorting networks on 13 inputs need 45 comparators

A mix of human-written and AI-generated textHuman understanding: all partscs.DS — Data Structures and Algorithmsmath.CO — Combinatorics

Contributed by Tejasvi Singh Tomar

Version 2 / Oct 26, 2026 / CC BY 4.0

Abstract

Let S(N)S(N) be the least number of comparators in a sorting network on NN inputs (the Bose–Nelson problem). We prove S(13)≥45S(13)\ge45, so Juillé's network is optimal and S(13)=45S(13)=45. We also prove P(2,N)=⌈lg⁡F(N)⌉P(2,N)=\lceil\lg F(N)\rceil for 3≤N≤323\le N\le32, where P(2,N)P(2,N) is the least worst-case number of comparators met by the two largest inputs in a network that delivers them to fixed outputs, and FF is an explicit function of Van Voorhis. This proves the twenty tabulated lower bounds on S(N)S(N) for 13≤N≤3213\le N\le32, which rested on an inequality of Van Voorhis whose published proof is invalid, and S(13)=45S(13)=45 raises each of them by one. Both proofs use computer searches. Harder's method for S(11)=35S(11)=35 applies Van Voorhis's one-value argument to the set of 00-11 vectors that a prefix of a network produces; for S(13)≥45S(13)\ge45 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 S(11)=35S(11)=35 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.

Author comments: This 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.

References

  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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
  8. J. Harder, An answer to the Bose--Nelson sorting problem for 11 and 12 channels , arXiv:2012.04400v3 [cs.DS], 2022.arXiv
  9. 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
  10. 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
  1. 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.
  2. D. E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching , 2nd ed., Addison-Wesley, Reading, MA, 1998.
  3. 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
  4. 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
  5. 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
  6. T. S. Tomar, , GitHub repository, , commit .
  7. T. S. Tomar, Certificate and verifier for ``Sorting networks on 13 inputs need 45 comparators'' , Zenodo, 2026, doi: (https://doi.org/\suppdoi).link
  8. 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
  9. 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
  10. 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
  11. 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
  12. 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
  13. 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

  1. v1 · 47 pagesSubmitted by Tejasvi Singh TomarInitial depositSupersededOct 26, 2026
  2. 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