The "perfect shuffle" permutation of order $n$ is defined to be the permutation:
where n is an even number. For example, the perfect shuffle on six elements, rho(6) = (1 2 4)(3 6 5), maps the list "abcdef" to the list "daebfc". The name is taken from that method of shuffling a deck of cards that cuts the deck into halves and then interleaves the two halves perfectly.
We have in mind permuting, in-place, a list represented by a one dimensional array of elements indexed by the integers 1 through n. By in-place we mean without the use of substantial extra space over and above that which the list elements already occupy. To be precise, we allow ourselves no more than O(log ^2 n) extra bits for program variables and data structures.
Permutations are made up of disjoint cycles and it is easy to move all the elements of one cycle, using just one extra location, by a so called ``cycle leader'' algorithm. That method proceeds by repeatedly making a space in the list, computing the index of the element that belongs in that space and moving that element, so creating a new space.
If we can easily find a place to start a new cycle when the current cycle terminates then the entire task becomes easy. This is the case for some commonly used permutations such as reversal and cyclic shift. A method already presented in In-Situ, Stable Merging by way of the Perfect Shuffle achieves the perfect shuffle in-place and in linear time at the expense of using about twice the number of element moves used by the method described in this paper. This is done by reducing the general case to the special case of permutations of length a power of 2.
In this paper we investigate an alternative approach, namely computing the position of representative elements of the cycles in the general case. We analyse the structure of the permutation in terms of the size, number and location of its cycles. Then we construct a procedure that computes a set of representative elements, in-place and in linear time. A cycle leader algorithm can use this set to realise the perfect shuffle in-place and in linear time.