%I A036604
%S A036604 0,1,3,5,7,10,13,16,19,22,26,30,34,38
%N A036604 Sorting numbers: minimal number of comparisons needed to sort n elements.
%C A036604 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 A036604 D. E. Knuth, Art of Computer Programming, Vol. 3, 2nd. edition, Sect.
5.3.1.
%D A036604 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.
%D A036604 Marcin Peczarski, New Results in Minimum-Comparison Sorting. Algorithmica
40(2):133-145, 2004.
%D A036604 E. Reingold, J. Nievergelt and N. Deo, Combinatorial Algorithms, Prentice-Hall,
1977, section 7.4, p. 309.
%D A036604 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 A036604 M. Peczarski, <a href="http://cat.inist.fr/?aModele=afficheN&cpsidt=18416105">
The Ford-Johnson algorithm still unbeaten for less than 47 elements</
a>
%H A036604 <a href="Sindx_So.html#sorting">Index entries for sequences related to
sorting</a>
%Y A036604 A001768 is an upper bound, A003070 a lower bound.
%Y A036604 Sequence in context: A062430 A016040 A003070 this_sequence A001768 A089108
A029899
%Y A036604 Adjacent sequences: A036601 A036602 A036603 this_sequence A036605 A036606
A036607
%K A036604 nonn,nice,hard
%O A036604 1,3
%A A036604 N. J. A. Sloane (njas(AT)research.att.com).
%E A036604 a(13) was determined by Marcin Peczarski. - Bodo Manthey, Sep 25 2002.
%E A036604 a(14)=38 and a(22)=71 were determined by Marcin Peczarski. - Bodo Manthey
(manthey(AT)cs.uni-sb.de), Feb 28 2007
|
