PERMUTING IN-PLACE

This paper addresses the fundamental problem of permuting the elements of an array of n elements according to some given permutation. It aim s to perform the permutation quickly by using only a polylogarithmic n umber 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 (amor tised) unit cost. This algorithm requires O (n log n) time and O (1) w ords 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 valu es are all distinct and are either initially in sorted order or will b e when permuted.