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
An estimate. The probability that Bogosort doesn't sort the deck in a particular shuffle is $1 - \frac{1}{52!}$, hence $1 - B(n) = \left( 1 - \frac{1}{52}! \right)^n$. Since
$$\left( 1 - \frac{x}{n} \right)^n \approx e^{-x}$$
for large $n$, the above is is approximately equal to $e^{- \frac{n}{52!} }$, hence $B(n) \approx 0.9$ when
$$- \frac{n}{52!} \approx \log 0.1 \approx -2.30.$$
This gives
$$n \approx 2.30 \cdot 52! \approx 2.30 \cdot \sqrt{106\pi} \left( \frac{52}{e} \right)^{52} \approx 1.87 \times 10^{68}$$
by Stirling's approximation. By comparison, the current age of the universe is about $4.33 \times 10^{17}$ seconds, or about $4.33 \times 10^{32}$ flops if your computer runs at $1$ petaflops.