cp's OEIS Frontend

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

%I A001768 M2408 N0954 #53 Feb 16 2025 08:32:24
%S A001768 0,1,3,5,7,10,13,16,19,22,26,30,34,38,42,46,50,54,58,62,66,71,76,81,
%T A001768 86,91,96,101,106,111,116,121,126,131,136,141,146,151,156,161,166,171,
%U A001768 177,183,189,195,201,207,213,219,225,231,237,243,249,255
%N A001768 Sorting numbers: number of comparisons for merge insertion sort of n elements.
%D A001768 D. E. Knuth, Art of Computer Programming, Vol. 3, Sect. 5.3.1.
%D A001768 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.
%D A001768 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A001768 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A001768 Alois P. Heinz, <a href="/A001768/b001768.txt">Table of n, a(n) for n = 1..10000</a> (first 1000 terms from T. D. Noe)
%H A001768 J.-P. Allouche and J. Shallit, <a href="http://www.cs.uwaterloo.ca/~shallit/Papers/as0.ps">The ring of k-regular sequences</a>, Theoretical Computer Sci., 98 (1992), 163-197.
%H A001768 J.-P. Allouche and J. Shallit, <a href="http://dx.doi.org/10.1016/0304-3975(92)90001-V">The ring of k-regular sequences</a>, Theoretical Computer Sci., 98 (1992), 163-197.
%H A001768 L. R. Ford, Jr. and S. M. Johnson, <a href="http://www.jstor.org/stable/2308750">A tournament problem</a>, Amer. Math. Monthly, 66 (1959), 387-389.
%H A001768 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Sorting.html">Sorting</a>
%H A001768 <a href="/index/So#sorting">Index entries for sequences related to sorting</a>
%F A001768 a(n) = Sum_{k=1..n} ceiling(log_2 (3k/4)). See also Problem 5.3.1-14 of Knuth.
%F A001768 a(n) = n(z-1)-[(2^(z+2)-3z)/6] where z = [log_2(3n+3)]. - _David W. Wilson_, Feb 26 2006
%p A001768 Digits := 60: A001768 := proc(n) local k; add( ceil( log(3*k/4)/log(2) ), k=1..n); end;
%p A001768 # second Maple program:
%p A001768 b:= proc(n) option remember; ceil(log[2](3*n/4)) end:
%p A001768 a:= proc(n) option remember; `if`(n<1, 0, a(n-1)+b(n)) end:
%p A001768 seq(a(n), n=1..61);  # _Alois P. Heinz_, Dec 03 2019
%t A001768 Accumulate[Ceiling[Log[2,(3*Range[60])/4]]] (* _Harvey P. Dale_, Oct 30 2013 *)
%o A001768 (PARI) a(n)=ceil(log(3/4*n)/log(2)) \\ _Charles R Greathouse IV_, Nov 04 2011
%o A001768 (Haskell)
%o A001768 a001768 n = n * (z - 1) - (2 ^ (z + 2) - 3 * z) `div` 6
%o A001768    where z = a085423 $ n + 1
%o A001768 -- _Reinhard Zumkeller_, Mar 16 2013  after _David W. Wilson_'s formula.
%Y A001768 Cf. A085423, A000523.
%K A001768 nonn,easy,nice
%O A001768 1,3
%A A001768 _N. J. A. Sloane_
%E A001768 Name clarified by _Li-yao Xia_, Nov 18 2015