|
%I #33 Apr 09 2023 15:31:38
%S 0,1,3,5,7,10,13,16,19,22,26,30,34,38,42
%N Sorting numbers: minimal number of comparisons needed to sort n elements.
%C 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
%D D. E. Knuth, Art of Computer Programming, Vol. 3, 2nd. edition, Sect. 5.3.1.
%D E. Reingold, J. Nievergelt and N. Deo, Combinatorial Algorithms, Prentice-Hall, 1977, section 7.4, p. 309.
%D 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).]
%H Eisa Alanazi, Malek Mouhoub, Sandra Zilles, <a href="https://arxiv.org/abs/1801.03968">Interactive Learning of Acyclic Conditional Preference Networks</a>, arXiv:1801.03968 [cs.AI], 2018.
%H Marcin Peczarski, <a href="https://doi.org/10.1007/s00453-004-1100-7">New Results in Minimum-Comparison Sorting</a>, Algorithmica 40(2):133-145, 2004.
%H Marcin Peczarski, <a href="https://doi.org/10.1016/j.ipl.2006.09.001">The Ford-Johnson algorithm still unbeaten for less than 47 elements</a>, Information Processing Letters, Volume 101, Issue 3, 14 February 2007, Pages 126-128.
%H Marcin Peczarski, <a href="http://arxiv.org/abs/1108.0866">Towards optimal sorting of 16 elements</a>, arXiv:1108.0866 [cs.DS], 2011.
%H Marcin Peczarski, <a href="https://doi.org/10.1007/3-540-45749-6_68">Sorting 13 Elements Requires 34 Comparisons</a>, Proc. of the 10th European Symp. on Algorithms (ESA), vol. 2452 of Lecture Notes in Comput. Sci., pp. 785-794. Springer, 2002.
%H <a href="/index/So#sorting">Index entries for sequences related to sorting</a>
%Y A001768 is an upper bound, A003070 a lower bound.
%Y Cf. A360495.
%K nonn,nice,hard,more
%O 1,3
%A _N. J. A. Sloane_
%E a(13) was determined by Marcin Peczarski. - Bodo Manthey, Sep 25 2002
%E a(14)=38 and a(22)=71 were determined by Marcin Peczarski. - Bodo Manthey (manthey(AT)cs.uni-sb.de), Feb 28 2007
|
