cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

A003075 Minimal number of comparisons needed for n-element sorting network.

Original entry on oeis.org

0, 1, 3, 5, 9, 12, 16, 19, 25, 29, 35, 39
Offset: 1

Views

Author

Keywords

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).

Crossrefs

A006282 is an upper bound. Cf. A036604, A067782 (minimal depth).

Extensions

Updates from Ed Pegg Jr, Dec 05 2001
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
Entry revised by N. J. A. Sloane, Jun 02 2014
a(11)-a(12) from Jannis Harder, Dec 10 2019