HEXAGONbeta

Sorting networks on 13 inputs need at least 44 comparators

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

Contributed by Tejasvi Singh Tomar ↗

Version 1 / Nov 12, 2026 / CC BY 4.0

Abstract

Let S(N)S(N) be the least number of comparators in a sorting network on NN inputs. We prove S(13)≥44S(13)\ge44, one more than the previously best proved lower bound. We also prove P(2,N)=⌈log⁡2F(N)⌉P(2,N)=\lceil \log_2 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; the lower bound comes from a finite search based on the structure of the paths of these two values. Starting from Harder's S(11)=35S(11)=35 and S(12)=39S(12)=39, these values of P(2,N)P(2,N), the two-value bound S(N)≥S(N−2)+P(2,N)S(N)\ge S(N-2)+P(2,N) and the one-value bound S(N)≥S(N−1)+⌈log⁡2N⌉S(N)\ge S(N-1)+\lceil \log_2 N\rceil give the twenty lower bounds on S(N)S(N) for 13≤N≤3213\le N\le32 in Dobbelaere's table; these bounds rested on Van Voorhis's inequality P(2,N)≥⌈log⁡2F(N)⌉P(2,N)\ge\lceil \log_2 F(N)\rceil, whose published proof is invalid. The bound S(13)≥44S(13)\ge44 is also proved in Lean 4, with every step checked by Lean's kernel.

Author comments: Published on Zenodo: https://doi.org/10.5281/zenodo.23730883

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. 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
  4. R. W. Floyd and D. E. Knuth, The Bose--Nelson sorting problem , A Survey of Combinatorial Theory (J. N. Srivastava, ed.), 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
  5. 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
  6. J. Harder, An answer to the Bose--Nelson sorting problem for 11 and 12 channels , arXiv:2012.04400v3 [cs.DS], 2022.arXiv
  7. 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
  8. 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.
  9. D. E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching , 2nd ed., Addison-Wesley, Reading, MA, 1998.
  10. 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
Show all 19 referencesShow fewer references
  1. 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
  2. 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
  3. 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
  4. 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
  5. T. S. Tomar, Sorting networks on 13 inputs need 45 comparators , Zenodo, 2026, doi:10.5281/zenodo.23504358 (https://doi.org/10.5281/zenodo.23504358).DOI
  6. T. S. Tomar, , GitHub repository, , commit .
  7. T. S. Tomar, Lean formalization of S(13)≥44S(13)\ge44 , part of the supplement Supp .
  8. T. S. Tomar, Kernel-checked Lean formalization of S(13)≥44S(13)\ge44 , part of the supplement Supp .
  9. T. S. Tomar, Programs and logs for ``Sorting networks on 13 inputs need at least 44 comparators'' , Zenodo, 2026, doi: (https://doi.org/\suppdoi).link

Version history

  1. v1 · 20 pagesSubmitted by Tejasvi Singh TomarPublished on Zenodo: https://doi.org/10.5281/zenodo.23730883CurrentNov 12, 2026