A036604 Sorting numbers: minimal number of comparisons needed to sort n elements.

0, 1, 3, 5, 7, 10, 13, 16, 19, 22, 26, 30, 34, 38, 42, 46, 50, 54, 58, 62, 66, 71

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• nice
• hard
• more

Comments

The Peczarski paper in Algorithmica has a table giving upper and lower bounds that differ by at most 1. In particular, the values a(20) = 62 and a(21) = 66 are also known. - Bodo Manthey, Mar 01 2007

References

• D. E. Knuth, Art of Computer Programming, Vol. 3, 2nd. edition, Sect. 5.3.1.
• E. Reingold, J. Nievergelt and N. Deo, Combinatorial Algorithms, Prentice-Hall, 1977, section 7.4, p. 309.
• Tianxing Tao, On optimal arrangement of 12 points, pp. 229-234 in Combinatorics, Computing and Complexity, ed. D. Du and G. Hu, Kluwer, 1989. [Finds a(12).]

Links

• Eisa Alanazi, Malek Mouhoub, Sandra Zilles, Interactive Learning of Acyclic Conditional Preference Networks, arXiv:1801.03968 [cs.AI], 2018.
• Enrico Iurlano and Günther R. Raidl, SAT-Based Search for Minwise Independent Families, arXiv:2412.11811 [cs.DM], 2024. See p. 5.
• Marcin Peczarski, New Results in Minimum-Comparison Sorting, Algorithmica 40(2):133-145, 2004.
• Marcin Peczarski, The Ford-Johnson algorithm still unbeaten for less than 47 elements, Information Processing Letters, Volume 101, Issue 3, 14 February 2007, Pages 126-128.
• Marcin Peczarski, Towards optimal sorting of 16 elements, arXiv:1108.0866 [cs.DS], 2011.
• Marcin Peczarski, Sorting 13 Elements Requires 34 Comparisons, Proc. of the 10th European Symp. on Algorithms (ESA), vol. 2452 of Lecture Notes in Comput. Sci., pp. 785-794. Springer, 2002.
• Florian Stober and Armin Weiss, Lower bounds for sorting 16, 17, and 18 elements, 2023 Proc. Symp. Algorithm Engineering and Experiments pp. 201-213, 2023. SIAM; arXiv preprint, arXiv:2206.05597 [cs.DS], 2022.
• Index entries for sequences related to sorting

Crossrefs

A001768 is an upper bound, A003070 a lower bound.

Cf. A360495.

Extensions

a(13) was determined by Marcin Peczarski. - Bodo Manthey, Sep 25 2002

a(14)=38 and a(22)=71 were determined by Marcin Peczarski. - Bodo Manthey (manthey(AT)cs.uni-sb.de), Feb 28 2007

a(16)=46, a(17)=50, and a(18)=54 were determined by Stober and Weiss. - Robert McLachlan, May 29 2024

a(19)-a(22) from table in arXiv preprint of Stober and Weiss. - Domotor Palvolgyi, Jun 03 2025