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

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, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12, 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

Offset: 1

Author

N. J. A. Sloane, Nov 15 2011

Keywords

• nonn

References

• 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.
• F. K. Hwang and S. Lin, Optimal merging of 2 elements with n elementsw, Acta Informatica, 1 (1971), 145-158.

Links

• Index entries for sequences related to sorting

Crossrefs

Cf. A200310, A239100.

Programs

Maple

s:=[2,3];
for n from 4 to 13 do
  for i from A200310(n-1)+1 to A200310(n) do s:=[op(s),n]; od:
od:

Formula

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