A006282 -id:A006282 - cp's OEIS frontend

A083742 First differences of A006282.

0, 1, 2, 2, 4, 3, 4, 3, 7, 5, 6, 4, 7, 5, 6, 4, 11, 8, 9, 6, 10, 7, 8, 5, 11, 8, 9, 6, 10, 7, 8, 5, 16, 12, 13, 9, 14, 10, 11, 7, 15, 11, 12, 8, 13, 9, 10, 6, 16, 12, 13, 9, 14, 10, 11, 7, 15, 11, 12, 8, 13, 9, 10, 6, 22, 17, 18, 13, 19, 14, 15, 10, 20, 15, 16, 11, 17

Offset: 0

Ralf Stephan, May 05 2003

D. E. Knuth, Art of Computer Programming, Sorting and Searching, Addison-Wesley, 1973, Section 5.2.2, ex. 14,15.

J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197, ex. 29.

a(0)=0, a(2n)=a(n)+floor(log_2(2n)), a(2n+1)=a(n)+1.

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

Original entry on oeis.org

0, 1, 3, 5, 9, 12, 16, 19, 25, 29, 35, 39

Offset: 1

N. J. A. Sloane

It is conjectured that the sequence continues (after 39) 45, 51, 56, 60, ...
a(13) <= 45 is mentioned in Knuth, Sorting and Searching, Vol. 2. a(9) was determined in 1991. - Ed Pegg Jr, Dec 05 2001.
Correction: the value for a(9) was not determined in the 1991 reference, which instead is about optimal depth. - Michael Codish, Jun 01 2014

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.
H. Jullie, Lecture Notes in Comp. Sci. 929 (1995), 246-260.
D. E. Knuth, Art of Computer Programming, Vol. 3, Sect. 5.3.4, Eq. (11).
I. Parberry, "A Computer Assisted Optimal Depth Lower Bound for Nine-Input Sorting Networks", Mathematical Systems Theory, Vol. 24, pp. 101-116, 1991.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

D. Bundala, M. Codish, L. Cruz-Filipe et al., Optimal-Depth Sorting Networks, arXiv preprint arXiv:1412.5302 [cs.DS], 2014.
Michael Codish, Luís Cruz-Filipe, Michael Frank and Peter Schneider-Kamp, Twenty-Five Comparators is Optimal when Sorting Nine Inputs (and Twenty-Nine for Ten), arXiv:1405.5754 [cs.DM], 2014.
Bert Dobbelaere, Smallest and fastest sorting networks for a given number of inputs
Milton W. Green, Letter to N. J. A. Sloane, 1973 (note "A360" refers to N0360 which is A000788).
Jannis Harder, Lower Size Bounds for Sorting Networks
Mariana Nagy, Vlad-Florin Drăgoi and Valeriu Beiu, Employing Sorting Nets for Designing Reliable Computing Nets, IEEE 20th International Conference on Nanotechnology (IEEE-NANO 2020) 370-375.
Ian Parberry, A Computer Assisted Optimal Depth Lower Bound for Nine-Input Sorting Networks
Ed Pegg Jr., Illustration of initial terms
Index entries for sequences related to sorting

A006282 is an upper bound. Cf. A036604, A067782 (minimal depth).

Updates from Ed Pegg Jr, Dec 05 2001
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
Entry revised by N. J. A. Sloane, Jun 02 2014
a(11)-a(12) from Jannis Harder, Dec 10 2019

cp's OEIS Frontend

A083742 First differences of A006282.

Views

Author

Keywords

References

Links

Formula

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions