The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A036604 Sorting numbers: minimal number of comparisons needed to sort n elements. 4


%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.

%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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 25 04:03 EST 2021. Contains 341596 sequences. (Running on oeis4.)