login
This site is supported by donations to The OEIS Foundation.

 

Logo

Many excellent designs for a new banner were submitted. We will use the best of them in rotation.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A036604 Sorting numbers: minimal number of comparisons needed to sort n elements. 2
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.

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.

Marcin Peczarski, New Results in Minimum-Comparison Sorting. Algorithmica 40(2):133-145, 2004.

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

Table of n, a(n) for n=1..15.

Marcin Peczarski, The Ford-Johnson algorithm still unbeaten for less than 47 elements

Marcin Peczarski, Towards optimal sorting of 16 elements (2011), arXiv:1108.0866.

Index entries for sequences related to sorting

CROSSREFS

A001768 is an upper bound, A003070 a lower bound.

Sequence in context: A062430 A016040 A003070 * A001768 A089108 A186355

Adjacent sequences:  A036601 A036602 A036603 * A036605 A036606 A036607

KEYWORD

nonn,nice,hard

AUTHOR

N. J. A. Sloane.

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

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

Content is available under The OEIS End-User License Agreement .

Last modified April 20 16:20 EDT 2014. Contains 240806 sequences.