## Parallel and sequential in-place permuting and shuffling using involutions

Qingxuan Yang, Department of Computer Science, University of Peking, China.
John Ellis, Department of Computer Science, University of Victoria, Canada.
Khalegh Mamakani, Department of Computer Science, University of Victoria, Canada.
Frank Ruskey, Department of Computer Science, University of Victoria, Canada.

### Abstract:

We show that any permutation of $\{1,2,\ldots,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 in parallel in time $O(1)$. In the case where the permutation is the $k$-way perfect shuffle we develop two methods for efficiently computing such a pair of involutions. The first method works whenever $N$ is a power of $k$; in this case the time is $O(N)$ and space $O(\log^2 N)$. The second method applies to the general case where N is a multiple of $k$; here the time is $O(N \log N)$ and the space is $O(\log^2 N)$. If $k=2$ the space usage of the first method can be reduced to $O(log N)$ on a machine that has a SADD (population count) instruction.

• Appears in Information Processing Letters, 113 (2013) 386-391.
• Submitted to a conference and rejected, June 2012.
• Submitted to Information Processing Letters, April 9, 2012.
• The SADD instruction referred to in the abstract is from Don Knuth's MMIX machine. Of course, many other machines have an equivalent instruction.
• The program used in the timing of the algorithm: YER.c.
• Typos: There are some typos in the routine modInv$(M,r)$ in the paper.
• Line 2: $i \in \{1,2,\ldots,kM-2\}$
• Line 3: $x$ should be $i$.
• Line 4: $j := g\ (r(i/g)^{-1} \bmod{( kM-1)/g })$
We thank Sergio Mergen for noting that there were some typos in this routine. Here is a link to some Maple code that generates the comparisons used in the figure: YERmaple.pdf.