In-place permuting and perfect shuffling using involutions

• Finds two involutions whose product is the perfect k-way perfect shuffle if N is a power of k.
• Method is efficient both in terms of time O(N) and space .
• A second method is developed for the case where N is a multiple of k.
• Both methods can be represented by a variant of comparator networks with two rounds of simultaneous swaps.

Every permutation of {1,2,…,N} can be written as the product of two involutions. As a consequence, any permutation of the elements of an array can be performed in-place using simultaneous swaps in two rounds of swaps. In the case where the permutation is the k-way perfect shuffle, we develop two methods for efficiently computing the pair of involutions that accomplishes these swaps.The first method works whenever N is a power of k; in this case the time is O(N) and space . The second method applies to the general case where N is a multiple of k; here the time is and the space is . If k=2 the space usage of the first method can be reduced to on a machine that has a SADD (population count) instruction.