login
Number of comparisons needed for optimal merging of 2 elements with n elements.
1

%I #13 Sep 23 2016 10:03:14

%S 2,3,4,5,5,6,6,6,7,7,7,7,8,8,8,8,8,8,9,9,9,9,9,9,9,9,10,10,10,10,10,

%T 10,10,10,10,10,10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,

%U 12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,13,13,13,13,13,13,13

%N Number of comparisons needed for optimal merging of 2 elements with n elements.

%D R. L. Graham, On sorting by comparisons, in Proceedings of the ATLAS Symposium, 1971, pp. 263-269; http://www.math.ucsd.edu/~ronspubs/71_07_sorting.pdf.

%D F. K. Hwang and S. Lin, Optimal merging of 2 elements with n elementsw, Acta Informatica, 1 (1971), 145-158.

%H <a href="/index/So#sorting">Index entries for sequences related to sorting</a>

%F Let f(i) = A200310(i). Then for i in the range f(n-1)+1 through f(n), a(i) = n.

%p s:=[2,3];

%p for n from 4 to 13 do

%p for i from A200310(n-1)+1 to A200310(n) do s:=[op(s),n]; od:

%p od:

%Y Cf. A200310, A239100.

%K nonn

%O 1,1

%A _N. J. A. Sloane_, Nov 15 2011