|
|
A003075
|
|
Minimal number of comparisons needed for n-element sorting network.
(Formerly M2446)
|
|
6
|
|
|
0, 1, 3, 5, 9, 12, 16, 19, 25, 29, 35, 39
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
It is conjectured that the sequence continues (after 39) 45, 51, 56, 60, ...
a(13) <= 45 is mentioned in Knuth, Sorting and Searching, Vol. 2. a(9) was determined in 1991. - Ed Pegg Jr, Dec 05 2001.
Correction: the value for a(9) was not determined in the 1991 reference, which instead is about optimal depth. - Michael Codish, Jun 01 2014
|
|
REFERENCES
|
R. W. Floyd and D. E. Knuth, The Bose-Nelson sorting problem, pp. 163-172 of J. N. Srivastava, ed., A Survey of Combinatorial Theory, North-Holland, 1973.
H. Jullie, Lecture Notes in Comp. Sci. 929 (1995), 246-260.
D. E. Knuth, Art of Computer Programming, Vol. 3, Sect. 5.3.4, Eq. (11).
I. Parberry, "A Computer Assisted Optimal Depth Lower Bound for Nine-Input Sorting Networks", Mathematical Systems Theory, Vol. 24, pp. 101-116, 1991.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
|
|
CROSSREFS
|
|
|
KEYWORD
|
hard,more,nonn,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
Correction and update: terms are exact for n<=10. The precise values for n=9 and n=10 are established in the reference from 2014 by Codish et al. - Michael Codish, Jun 01 2014
|
|
STATUS
|
approved
|
|
|
|