|
Search: id:A003075
|
|
|
| A003075 |
|
Minimal number of comparisons needed for n-element sorting network.
(Formerly M2446)
|
|
+0
4
|
|
| 0, 1, 3, 5, 9, 12, 16, 19, 25, 29, 35, 39, 45, 51, 56, 60
(list; graph; listen)
|
|
|
OFFSET
|
1,3
|
|
|
COMMENT
|
a(13) <= 45 mentioned in Knuth, Sorting and Searching, Vol. 2. a(9) determined in 1991. - Ed Pegg Jr (ed(AT)mathpuzzle.com), Dec 05 2001
|
|
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.
|
|
LINKS
|
Ed Pegg Jr., Illustration of initial terms
J. H. Smith, Nine-Input Sorting Networks
Index entries for sequences related to sorting
|
|
CROSSREFS
|
A006282 is an upper bound. Cf. A036604.
Sequence in context: A120806 A020946 A091785 this_sequence A061562 A006282 A086845
Adjacent sequences: A003072 A003073 A003074 this_sequence A003076 A003077 A003078
|
|
KEYWORD
|
hard,nonn,nice
|
|
AUTHOR
|
njas
|
|
EXTENSIONS
|
Terms are exact for n<=9, otherwise the best known (according to Knuth).
Updates from Ed Pegg Jr (ed(AT)mathpuzzle.com), Dec 05 2001
|
|
|
Search completed in 0.002 seconds
|
