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

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.

CROSSREFS

KEYWORD

nonn,nice,hard,more

AUTHOR

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