Is there a linear time in-place riffle shuffle algorithm? This is the algorithm that some especially dextrous hands are capable of performing: evenly dividing an even-sized input array, and then interleaving the elements of the two halves.
Mathworld has a brief page on riffle shuffle. In particular, I'm interested in the out-shuffle variety which transforms the input array 1 2 3 4 5 6 into 1 4 2 5 3 6. Note that in their definition, the input length is $2n$.
It's straightforward to perform this in linear time if we've got a second array of size $n$ or more handy. First copy the last $n$ elements to the array. Then, assuming 0-based indexing, copy the first $n$ elements from indices $[0,1,2,...,n-1]$ to $[0, 2, 4,...,2n-2]$. Then copy the $n$ elements from the second array back to the input array, mapping indices $[0,1,2,...,n-1]$ to $[1,3,5,...,2n-1]$. (We can do slightly less work than that, because the first and last elements in the input do not move.)
One way of attempting to do this in-place involves the decomposition of the permutation into disjoint cycles, and then rearranging the elements according to each cycle. Again, assuming 0-based indexing, the permutation involved in the 6 element case is $$ \sigma=\begin{pmatrix} 0 & 1 & 2 & 3 & 4 & 5 \\ 0 & 2 & 4 & 1 & 3 & 5\end{pmatrix}=\begin{pmatrix}0 \end{pmatrix} \begin{pmatrix}5 \end{pmatrix} \begin{pmatrix}1 & 2 & 4 &3 \end{pmatrix}. $$
As expected, the first and last elements are fixed points, and if we permute the middle 4 elements we get the expected outcome.
Unfortunately, my understanding of the mathematics of permutations (and their $\LaTeX$) is mostly based on wikipedia, and I don't know if this can be done in linear time. Maybe the permutations involved in this shuffling can be quickly decomposed? Also, we don't even need the complete decomposition. Just determining a single element of each of the disjoint cycles would suffice, since we can reconstruct the cycle from one of its elements. Maybe a completely different approach is required.
Good resources on the related mathematics are just as valuable as an algorithm. Thanks!