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

Offset

1,3

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

Table of n, a(n) for n=1..18.

Eisa Alanazi, Malek Mouhoub, Sandra Zilles, Interactive Learning of Acyclic Conditional Preference Networks, arXiv:1801.03968 [cs.AI], 2018.

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.

Index entries for sequences related to sorting

Crossrefs

A001768 is an upper bound, A003070 a lower bound.

Cf. A360495.

Sequence in context: A062430 A016040 A003070 * A001768 A327672 A329815

Adjacent sequences: A036601 A036602 A036603 * A036605 A036606 A036607

Keyword

nonn,nice,hard,more

Author

N. J. A. Sloane

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

Status

approved