A003075 - OEIS

This site is supported by donations to The OEIS Foundation.

A003075

Minimal number of comparisons needed for n-element sorting network.
(Formerly M2446)

0, 1, 3, 5, 9, 12, 16, 19, 25, 29, 35, 39, 45, 51, 56, 60 (list; graph; refs; listen; history; internal format)

	OFFSET	`1,3`
	COMMENTS	`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.` `N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).`
	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: A020946 A091785 A191403 * A061562 A006282 A086845` `Adjacent sequences: A003072 A003073 A003074 * A003076 A003077 A003078`
	KEYWORD	`hard,nonn,nice`
	AUTHOR	`N. J. A. Sloane (njas(AT)research.att.com).`
	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`

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

Last modified February 17 06:27 EST 2012. Contains 205998 sequences.