A117627 Let f(n) = minimum of average number of comparisons needed for any sorting method for n elements and let g(n) = n!*f(n). Sequence gives a lower bound on g(n).

0, 2, 16, 112, 832, 6896, 62368, 619904, 6733312, 79268096, 1010644736, 13833177088, 203128772608, 3175336112128, 52723300200448, 927263962759168, 17221421451378688, 336720980854571008, 6911300635636400128, 148661140496700932096

Offset: 1

Author

N. J. A. Sloane, Oct 06 2006

Keywords

• nonn

Comments

Sorting methods have been constructed such that the lower bound of f(n) is achieved for n=1, 2, 3, 4, 5, 6, 9 and 10. Y. Césari was the first to show that f(7) is not obtainable. He also constructed optimal solutions for n=9 and 10. L. Kollár showed that the minimum number of comparisons needed for n=7 is 62416. - Dmitry Kamenetsky, Jun 11 2015

References

• Y. Césari, Questionnaire codage et tris, PhD Thesis, University of Paris, 1968.
• D. E. Knuth, TAOCP, Vol. 3, Section 5.3.1.

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..450
• L. Kollár, Optimal sorting of seven element sets, Proceedings of the 12th symposium on Mathematical foundations of computer science 1986, 449-457.
• Index entries for sequences related to sorting

Crossrefs

Cf. A003070, A036604, A117628.

Programs

Maple

q:= n-> ceil(log[2](n!)):
a:= n-> (q(n)+1)*n! - 2^q(n):
seq(a(n), n=1..30);  # Alois P. Heinz, Jun 11 2015

Mathematica

q[n_] := Log[2, n!] // Ceiling; a[n_] := (q[n]+1)*n! - 2^q[n]; Array[a, 20] (* Jean-François Alcover, Feb 13 2016 *)

PARI

a(n) = { my(N=n!, q = ceil(log(N)/log(2))); return ((q+1)*N - 2^q);} \\ Michel Marcus, Apr 21 2013

Formula

Knuth gives an explicit formula.

a(n) = (q(n)+1)*n! - 2^q(n) with q(n) = A003070(n).