login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

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
OFFSET
1,3
COMMENTS
Or, minimal depth of a sorting network on n channels.
REFERENCES
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.
LINKS
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).)
CROSSREFS
Cf. A003075.
Sequence in context: A375785 A054847 A335266 * A318916 A035299 A338215
KEYWORD
hard,nonn,nice,more
AUTHOR
Ron Zeno (rzeno(AT)hotmail.com), Feb 06 2002
EXTENSIONS
a(17) = 10 is mentioned in Ehlers (2017). - N. J. A. Sloane, Aug 21 2017
STATUS
approved