|
| |
|
|
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
(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, 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
|
| |
|
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
| |
|
STATUS
|
approved
|
| |
|
|
