Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%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