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!)
A067782 Minimal delay time for an n-element sorting network. 1
0, 1, 3, 3, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 9, 9, 10 (list; graph; refs; listen; history; text; internal format)



Or, minimal depth of a sorting network on n channels.


S. W. A.-H. Baddar, K. E. Batcher, Designing Sorting Networks: A New Paradigm, Springer (2011)

D. Bundala, J. Závodný, Optimal sorting networks, LATA 2014, LNCS, vol. 8370, Springer (2014), pp. 236-247

Thorsten Ehlers, Merging almost sorted sequences yields a 24-sorter, Information Processing Letters, Volume 118, February 2017, Pages 17-20

D. E. Knuth, Art of Computer Programming, Vol. 3, Sect. 5.3.4.


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

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

T. Ehlers, M. Müller, Faster sorting networks for 17, 19 and 20 inputs, arXiv:1410.2736 [cs.DS], 2014.

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.

I. Parberry, A Computer Assisted Optimal Depth Lower Bound for Nine-Input Sorting Networks, Mathematical Systems Theory, Vol. 24, pp. 101-116, 1991. (Determines a(9) and a(10).)

Index entries for sequences related to sorting


Cf. A003075.

Sequence in context: A075260 A054847 A335266 * A318916 A035299 A338215

Adjacent sequences:  A067779 A067780 A067781 * A067783 A067784 A067785




Ron Zeno (rzeno(AT)hotmail.com), Feb 06 2002


a(17) = 10 is mentioned in Ehlers (2017). - N. J. A. Sloane, Aug 21 2017



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 January 23 01:37 EST 2021. Contains 340384 sequences. (Running on oeis4.)