Complexity of applying a permutation in-place
Option 0: Permuting In Place (1995) by Faith E. Fich , J. Ian Munro , Patricio V. Poblete $O(n \log n)$ time $O( \log^{2} n )$ space.

Option 1: Cheat by compressing your permutation to a succinct data structure, see Munro  http://www.itu.dk/people/ssrao/icalp03-a.pdf .

Option 2:  Use a prime cycle decomposition to store the perm succinctly and use that extra space to cheat http://oeis.org/A186202 

Option 3: Keep track of the largest index of each cycle manipulated. For each iteration use the largest unseen index to move everything in its cycle by one. If it hits a seen index undo all that work because the cycle has already been manipulated. $O(n^2)$ time, $O(\#\text{cycles} * \log n)$ space.

Option 4: Keep track of the largest index of each cycle manipulated, but only do them in batches of distinct cycle lengths. For each iteration use the largest unseen index to move everything in it's cycle by one. If it hits a seen index undo all that work because thae cycle has already been manipulated. $O(n^2 * \text{distinct}\_\text{cycle}\_\text{lengths})$ time, $O((\#\text{cycles}\_\text{with}\_\text{same}\_\text{size}) * \log n)$ space.

Option 5: From same paper by Munro as Option 0, For $i = 1 .. n$ rotate the cycle of $p(i)$ if $i$ is the largest index in that cycle. $O(n^2)$ time and $O(\log  n)$ space.