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

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

Crossrefs

Cf. A003075.

Sequence in context: A075260 A054847 A335266 * A318916 A035299 A338215

Adjacent sequences: A067779 A067780 A067781 * A067783 A067784 A067785

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