Linear time in-place riffle shuffle algorithm
The problem is surprisingly non-trivial. Here is a nice solution by Ellis and Markov, In-Situ, Stable Merging by way of the Perfect Shuffle (section 7). Ellis, Krahn and Fan, Computing the Cycles in the Perfect Shuffle Permutation succeed in selecting "cycle leaders", at the expense of more memory. Also related is the nice paper by Fich, Munro and Poblete, Permuting In Place, which gives a general $O(n\log n)$ time algorithm for the oracle model. If only an oracle for the permutation is available, the algorithm requires logarithmic space; if we also have an oracle for the inverse, it requires constant space.

Now for Ellis and Markov's solution. First, suppose $n = x+y$. Then computing the perfect shuffle of order $n$ reduces to computing the perfect shuffle of orders $x$ and $y$, with a rotation preceding them. Here is a proof by example ($n=5$, $x=3$, $y=2$):
$$
\begin{array}{cc}
012\mathbf{345} &amp; \mathbf{67}89 \\
012\mathbf{567} &amp; \mathbf{34}89 \\
051627 &amp; 3849
\end{array}
$$

Ellis and Markov found an easy way to compute the perfect shuffle when $n=2^k$, using constant space and linear time. Using this, we obtain an algorithm for computing the perfect shuffle for arbitrary $n$. First, write $n = 2^{k_0} + \cdots + 2^{k_w}$ using the binary encoding of $n$, and let $n_i = 2^{k_i} + \cdots + 2^{k_w}$. Rotate the middle $n_0$ bits, shuffle the right-hand $2^{k_0}$ bits. Ignoring the righthand $2^{k_0}$ bits, rotate the middle $n_1$ bits, and shuffle the right-hand $2^{k_1}$ bits. And so on. Note that rotation is easy since the first few elements rotated function as cycle leaders. The total complexity of rotation is $O(n_0 + \cdots + n_w) = O(n)$, since $n_{t+1} &lt; n_t/2$. The total complexity of the inner shuffles is $O(2^{k_0} + \cdots + 2^{k_w}) = O(n)$.

It remains to show how to compute the perfect shuffle when $n=2^k$. In fact, we will be able to identify cycle leaders, following classical work on necklaces (Fredricksen and Maiorana, Necklaces of beads in $k$ colors and $k$-ary de Bruijn sequences; Fredricksen and Kessler, An algorithm for generating necklaces of beads in two colors).

What is the connection? I claim that the shuffle permutation corresponds to right shifting of the binary representation. Here is a proof by example, for $n=8$:
$$
\begin{array}{cccccccc}
000 &amp; 001 &amp; 010 &amp; 011 &amp; 100 &amp; 101 &amp; 110 &amp; 111 \\
000 &amp; 100 &amp; 001 &amp; 101 &amp; 010 &amp; 110 &amp; 011 &amp; 111
\end{array}
$$
Therefore, to find cycle leaders, we need to find one representative out of each equivalence class of the rotation of binary strings of length $k$. The papers mentioned above give the following algorithm for generating all cycle leaders. Start with $0^k$. At each step, we are at some point $a_1 \ldots a_k$. Find the maximal index $i$ of a zero bit, divide $k$ by $i$ to obtain $k = d\cdot i + r$, and let the following point be $(a_1\ldots a_{i-1}1)^d a_1\ldots a_r$. Whenever $r = 0$, the new string is a cycle leader.

For example, when $n=16$ this generates the sequence
$$
\mathbf{0000}, \mathbf{0001}, 0010, \mathbf{0011},
\mathbf{0101}, 0110, \mathbf{0111}, \mathbf{1111}.
$$

The cycle leaders are highlighted.