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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A003075 Minimal number of comparisons needed for n-element sorting network.
(Formerly M2446)
6
0, 1, 3, 5, 9, 12, 16, 19, 25, 29 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

It is conjectured that the sequence continues (after 29) 35, 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

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

D. Bundala, M. Codish, L. Cruz-Filipe et al., Optimal-Depth Sorting Networks, arXiv preprint arXiv:1412.5302 [cs.DS], 2014.

Michael Codish, Luís Cruz-Filipe, Michael Frank, Peter Schneider-Kamp, Twenty-Five Comparators is Optimal when Sorting Nine Inputs (and Twenty-Nine for Ten), arXiv:1405.5754 [cs.DM], 2014.

Bert Dobbelaere, Smallest and fastest sorting networks for a given number of inputs

Milton W. Green, Letter to N. J. A. Sloane, 1973.

Ian Parberry, A Computer Assisted Optimal Depth Lower Bound for Nine-Input Sorting Networks

Ed Pegg Jr., Illustration of initial terms

Index entries for sequences related to sorting

CROSSREFS

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

Sequence in context: A191403 A233779 A287105 * A061562 A006282 A086845

Adjacent sequences:  A003072 A003073 A003074 * A003076 A003077 A003078

KEYWORD

hard,nonn,nice

AUTHOR

N. J. A. Sloane

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

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 15 22:25 EDT 2019. Contains 328038 sequences. (Running on oeis4.)