cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

A003075 Minimal number of comparisons needed for n-element sorting network.

This page as a plain text file.
%I A003075 M2446 #69 Mar 12 2022 22:41:51
%S A003075 0,1,3,5,9,12,16,19,25,29,35,39
%N A003075 Minimal number of comparisons needed for n-element sorting network.
%C A003075 It is conjectured that the sequence continues (after 39) 45, 51, 56, 60, ...
%C A003075 a(13) <= 45 is mentioned in Knuth, Sorting and Searching, Vol. 2. a(9) was determined in 1991. - _Ed Pegg Jr_, Dec 05 2001.
%C A003075 Correction: the value for a(9) was not determined in the 1991 reference, which instead is about optimal depth. - _Michael Codish_, Jun 01 2014
%D A003075 R. W. Floyd and D. E. Knuth, The Bose-Nelson sorting problem, pp. 163-172 of J. N. Srivastava, ed., A Survey of Combinatorial Theory, North-Holland, 1973.
%D A003075 H. Jullie, Lecture Notes in Comp. Sci. 929 (1995), 246-260.
%D A003075 D. E. Knuth, Art of Computer Programming, Vol. 3, Sect. 5.3.4, Eq. (11).
%D A003075 I. Parberry, "A Computer Assisted Optimal Depth Lower Bound for Nine-Input Sorting Networks", Mathematical Systems Theory, Vol. 24, pp. 101-116, 1991.
%D A003075 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A003075 D. Bundala, M. Codish, L. Cruz-Filipe et al., <a href="http://arxiv.org/abs/1412.5302">Optimal-Depth Sorting Networks</a>, arXiv preprint arXiv:1412.5302 [cs.DS], 2014.
%H A003075 Michael Codish, Luís Cruz-Filipe, Michael Frank and Peter Schneider-Kamp, <a href="http://arxiv.org/abs/1405.5754">Twenty-Five Comparators is Optimal when Sorting Nine Inputs (and Twenty-Nine for Ten)</a>, arXiv:1405.5754 [cs.DM], 2014.
%H A003075 Bert Dobbelaere, <a href="https://htmlpreview.github.io/?https://github.com/bertdobbelaere/SorterHunter/blob/master/sorting_networks.html">Smallest and fastest sorting networks for a given number of inputs</a>
%H A003075 Milton W. Green, <a href="/A003075/a003075.pdf">Letter to N. J. A. Sloane, 1973</a> (note "A360" refers to N0360 which is A000788).
%H A003075 Jannis Harder, <a href="https://github.com/jix/sortnetopt">Lower Size Bounds for Sorting Networks</a>
%H A003075 Mariana Nagy, Vlad-Florin Drăgoi and Valeriu Beiu, <a href="https://doi.org/10.1109/NANO47656.2020.9183395">Employing Sorting Nets for Designing Reliable Computing Nets</a>, IEEE 20th International Conference on Nanotechnology (IEEE-NANO 2020) 370-375.
%H A003075 Ian Parberry, <a href="https://larc.unt.edu/ian/pubs/9-input.pdf">A Computer Assisted Optimal Depth Lower Bound for Nine-Input Sorting Networks</a>
%H A003075 Ed Pegg Jr., <a href="http://www.mathpuzzle.com/zenosort.gif">Illustration of initial terms</a>
%H A003075 <a href="/index/So#sorting">Index entries for sequences related to sorting</a>
%Y A003075 A006282 is an upper bound. Cf. A036604, A067782 (minimal depth).
%K A003075 hard,more,nonn,nice
%O A003075 1,3
%A A003075 _N. J. A. Sloane_
%E A003075 Updates from _Ed Pegg Jr_, Dec 05 2001
%E A003075 Correction and update: terms are exact for n<=10. The precise values for n=9 and n=10 are established in the reference from 2014 by Codish et al. - _Michael Codish_, Jun 01 2014
%E A003075 Entry revised by _N. J. A. Sloane_, Jun 02 2014
%E A003075 a(11)-a(12) from _Jannis Harder_, Dec 10 2019