Let $r$ denote the number of cards that, after shuffling $n$ cards, remain unsorted (the middle portion of the deck, that is to be suffled again).
Let $t_n$ be the needed number or shuffles starting from $n$ cards till all cards are sorted. We want $E(t_n)$
Now, lets consider that expectation conditioned on the value of $r_n$, i.e. suppose we know exactly how many cards remain unsorted after the first try:
Then we can write: $E[t_n | r_n=r] = 1 + E[t_r]$
(note that this includes the extreme cases $r_n=0$ and $r_n = n$)
Applying the property $E[E[x|y]] = E[x]$ we have:
$\displaystyle E[t_n] = \sum_{r=0}^n (1 + E[t_r]) \; p(n,r) $
where $p(n,r) = Prob(r_n = r)$ (we'll compute it later)
We must take out the term $r=n$ for the sum, and by trivial manipulation we get the desired recursion:
$\displaystyle
E[t_n] = \frac{1}{1-p(n,n)} \left( p(n,n) + \sum_{r=0}^{n-1} (1 + E[t_r]) \; p(n,r) \right) $
As initial values we have $E[t_0] = E[t_1] = 0$
To compute $p(n,r)$ (probability that after one shuffling of $n$ cards there remains -with the rules of our game- exactly $r$ cards to shuffle again) it's more simple (but more tedious), just combinatorial counting - i'll explain if you ask to.
My result is
$\displaystyle p(n,r) = \frac{(n + 1 -r) \; (r^2 - 3r + 3) \; (r-2)!}{n!}$
if $r>1$. Elsewhere, $p(n,0) = 1/n!$ and $p(n,1)=0$.
Here are some values (in javascript) http://hjg.com.ar/varios/mat/cards.html
BTW: This problem can be seen as in between two problems, one simpler and one more complex/general:
As compared to the Coupon Collector problem, this is more complicated, because we can't divide the road into "states" that will be visited sequentially - and hence we can simply express the desired expectation as a sum of expectations of those pieces.
It can be consisdered as a Markov Model with one absorbing state; but the markovian formulation, though apt, is too general, and the desired result (expected numbers of iterations to reach the absorbing state) is less straigforward that the solution proposed here. That's because our problem has some special restrictions (in terms of a Markov chain, we'd say that its transition matrix is triangular)
ADDED: To compute $p(n,r)$ , for $r \ge 2$ :
After shuffling $n$ cards, we get $r$ unsorted cards, say $(n1;r;n2)$ Lets count how many ways (with $n1$ $n2$ fixed) there are. They correspond to choose a permutation of the $r$ middle cards, with the condition that both extremes are "wrong". This is given by:
$r! - 2(r - 1)! + (r-2)! = (r^2 - 3 r + 3) (r-2)!$
(This is exclusion-inclusion counting: the first term counts all possibilities, the second count the cases where the first OR the last is right, the third count the cases where the first AND the last are right).
But, for a given $r$ there are several choices of $(n1;n2)$, they are only required to sum up $n-r$. Actually, there are $n - r +1$ alternatives. Then we get the total number of permutations that give $r$ unsorted cards, and divide over all the permutations:
$\displaystyle p(n,r) = \frac{(n + 1 -r) \; (r^2 - 3r + 3) \; (r-2)!}{n!}$
UPDATED: An asymptotic can be guessed (theoretically and empirically):
$\displaystyle E(t_n) \approx \frac{n(n-1)}{4} \approx \frac{n^2}{4}$
Best Answer
The Mexican Spiral shuffle is a permutation of $52$ (or $n$) items. You can find the order of the permutation, the number of repetitions that make it do nothing, by taking the lowest common multiple of its cycle lengths.
The shuffle is somewhat complex, so I don't think there is a simple formula based on the number of cards $n$. But you can just do the shuffle once on an ordered deck of n cards, examine the result to find its cycles, and then calculate the order from that.
Here is an example. I'll use $9$ cards.
The cards start off as
ABCDEFGHI, whereAis the top card. A single mexican spiral shuffle affects the cards like this:So the end results is that card
Awent to the location ofI, and cardIwent to the location ofE, and so on. We get the following cycles:A$\rightarrow$I$\rightarrow$E$\rightarrow$G$\rightarrow$F$\rightarrow$B$\rightarrow$AC$\rightarrow$H$\rightarrow$CD$\rightarrow$DThese cycles have lengths $6$, $2$, and $1$. The lowest common multiple of these lengths is $6$, so it takes $6$ shuffles for the cards to return to their original order.
If you do this with $52$ cards you'll find that the top card is part of a cycle of length $34$, the second card is in a cycle of length $10$, the fifth card is in a cycle of length $6$, and finally the 12th and 35th cards don't move (i.e. cycles of length $1$). The LCM of $34,10,6,1,1$ is $510$.