Strictly In-Place Algorithms for Permuting and Inverting Permutations

Bartłomiej Dudek, Paweł Gawrychowski, Karol Pokorski

We revisit the problem of permuting an array of length $n$ according to a given permutation in place, that is, using only a small number of bits of extra storage. Fich, Munro and P…