A067782 Minimal delay time for an n-element sorting network.

0, 1, 3, 3, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 9, 9, 10

Offset: 1

Author

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

Keywords

• hard
• nonn
• nice
• more

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).)
• Index entries for sequences related to sorting

Crossrefs

Cf. A003075.

Extensions

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