# Sorting a deck of cards with Bogosort

Suppose you have a standard deck of 52 cards which you would like to sort in a particular order. The notorious algorithm Bogosort works like this:

1. Shuffle the deck
2. Check if the deck is sorted. If it's not sorted, goto 1. If it's sorted, you're done.

Let B(n) be the probability that Bogosort sorts the deck in n shuffles or less. B(n) is a monotonically increasing function which converges toward 1. What is the smallest value of n for which B(n) exceeds, say, 0.9?

If the question is computationally infeasible then feel free to reduce the number of cards in the deck.

-

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.

-
Better go put the kettle on while I wait for this deck to get sorted then.. – Sputnik Jun 4 '11 at 21:49