Permuting in Place

Abstract

This paper addresses the fundamental problem of permuting the elements of an array of n elements according to some given permutation. It aims to perform the permutation quickly by using only a polylogarithmic number of bits of extra storage. The main result is an algorithm whose worst case running time is $O(n \log n)$ and uses $O(\log n)$ additional $\log n$-bit words of memory. A simpler method is presented for the case in which both the permutation and its inverse can be computed at (amortised) unit cost. This algorithm requires $O(n \log n)$ time and $O(1)$ words in the worst case. These results are extended to the situation in which a power of the permutation must be applied. A linear time, $O(1)$ word method is presented for the special case in which the data values are all distinct and are either initially in sorted order or will be when permuted.