A001768 Sorting numbers: number of comparisons for merge insertion sort of n elements.

0, 1, 3, 5, 7, 10, 13, 16, 19, 22, 26, 30, 34, 38, 42, 46, 50, 54, 58, 62, 66, 71, 76, 81, 86, 91, 96, 101, 106, 111, 116, 121, 126, 131, 136, 141, 146, 151, 156, 161, 166, 171, 177, 183, 189, 195, 201, 207, 213, 219, 225, 231, 237, 243, 249, 255

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

References

• D. E. Knuth, Art of Computer Programming, Vol. 3, Sect. 5.3.1.
• T. A. J. Nicholson, A method for optimizing permutation problems and its industrial applications, pp. 201-217 of D. J. A. Welsh, editor, Combinatorial Mathematics and Its Applications. Academic Press, NY, 1971.
• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..10000 (first 1000 terms from T. D. Noe)
• J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.
• J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.
• L. R. Ford, Jr. and S. M. Johnson, A tournament problem, Amer. Math. Monthly, 66 (1959), 387-389.
• Eric Weisstein's World of Mathematics, Sorting
• Index entries for sequences related to sorting

Crossrefs

Cf. A085423, A000523.

Programs

Haskell

a001768 n = n * (z - 1) - (2 ^ (z + 2) - 3 * z) `div` 6
   where z = a085423 $ n + 1
-- Reinhard Zumkeller, Mar 16 2013  after David W. Wilson's formula.

Maple

Digits := 60: A001768 := proc(n) local k; add( ceil( log(3*k/4)/log(2) ), k=1..n); end;
# second Maple program:
b:= proc(n) option remember; ceil(log[2](3*n/4)) end:
a:= proc(n) option remember; `if`(n<1, 0, a(n-1)+b(n)) end:
seq(a(n), n=1..61);  # Alois P. Heinz, Dec 03 2019

Mathematica

Accumulate[Ceiling[Log[2,(3*Range[60])/4]]] (* Harvey P. Dale, Oct 30 2013 *)

PARI

a(n)=ceil(log(3/4*n)/log(2)) \\ Charles R Greathouse IV, Nov 04 2011

Formula

a(n) = Sum_{k=1..n} ceiling(log_2 (3k/4)). See also Problem 5.3.1-14 of Knuth.

a(n) = n(z-1)-[(2^(z+2)-3z)/6] where z = [log_2(3n+3)]. - David W. Wilson, Feb 26 2006

Extensions

Name clarified by Li-yao Xia, Nov 18 2015