A280970 Number of comparisons required to sort all permutations of [n] by MTF sort.

0, 0, 3, 25, 208, 1928, 20328, 244536, 3347328, 51858432, 902874240, 17523066240, 375931514880, 8842225904640, 226294152053760, 6258916573056000, 185978410684416000, 5906514709831680000, 199606607730561024000, 7150186413112651776000, 270578540735613960192000

Offset: 0

Author

Alois P. Heinz, Jan 11 2017

Keywords

• nonn

Comments

MTF sort is an (inefficient) sorting algorithm: the first element that is smaller than its predecessor is moved to front repeatedly until the sequence is sorted. Comparisons of adjacent elements always begin at the front and are continued until the last or the next element to be moved is found.

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..404
• Project Euler, Problem 523: First Sort I
• Wikipedia, Sorting algorithm
• Index entries for sequences related to sorting

Crossrefs

Cf. A279683.

Programs

Maple

a:= proc(n) option remember;
      `if`(n<2, 0, a(n-1)*n + (n-1)! * (2^n+(n-3)*n/2))
    end:
seq(a(n), n=0..20);
# second Maple program:
a:= proc(n) option remember;
     `if`(n<7, [0$2, 3, 25, 208, 1928, 20328][n+1],
     ((4*n^2-23*n+2)*a(n-1)-(5*n^3-28*n^2-n+54)*a(n-2)
      +(2*n-4)*(n^3-2*n^2-24*n+52)*a(n-3)
      -(4*n-8)*(n-4)*(n-3)^2*a(n-4))/(n-6))
    end:
seq(a(n), n=0..20);

Mathematica

Flatten[{0, Simplify[Table[n!*(n*(n-5)/4 - Pi*I - 1 - 2^(1+n)*LerchPhi[2, 1, 1+n]) , {n, 1, 20}]]}] (* Vaclav Kotesovec, Jan 12 2017 *)

Formula

a(n) = a(n-1)*n + (n-1)! * (2^n+(n-3)*n/2) for n>1, a(0) = a(1) = 0.

a(n) ~ (n-1)! * 2^(n+1). - Vaclav Kotesovec, Jan 12 2017