The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; graph; refs; listen; history; text; internal format)



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


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


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

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.

Jannis Harder, Lower Size Bounds for Sorting Networks

Mariana Nagy, Vlad-Florin Drăgoi, Valeriu Beiu, Employing Sorting Nets for Designing Reliable Computing Nets, IEEE 20th International Conference on Nanotechnology (IEEE-NANO 2020) 370-375.

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


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




N. J. A. Sloane


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



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 June 14 08:31 EDT 2021. Contains 345018 sequences. (Running on oeis4.)