

A036604


Sorting numbers: minimal number of comparisons needed to sort n elements.


5



0, 1, 3, 5, 7, 10, 13, 16, 19, 22, 26, 30, 34, 38, 42, 46, 50, 54
(list;
graph;
refs;
listen;
history;
text;
internal format)



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, PrenticeHall, 1977, section 7.4, p. 309.
Tianxing Tao, On optimal arrangement of 12 points, pp. 229234 in Combinatorics, Computing and Complexity, ed. D. Du and G. Hu, Kluwer, 1989. [Finds a(12).]


LINKS



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



