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