First off, I came up with the same algorithm as mentioned by Russell Easterly but I have an additional tweak.
This is the initial algorithm:
for each increasing index i from 1 to length of array
movealong the permutation cycle of the current elementstarting at$f(i)$ and
stop at the first permutation entry$k = f(j)$where$j \le i < k$
or else$k = NaN$
swap array element at i with element at kif k is not NaN
This alone has a worst-case which is only twice as fast as the algorithm in the OP. But the common average case is much faster. For infinitely large N – under consideration of the geometric distribution of randomly generated permutation functions with $p = P(f(j) > i) = 0.5$ for all $j,i$, we would get N times the expectancy value which is $\mathcal{O}(N)$ time complexity with $\mathcal{O}(1)$ space complexity but it might be worse for real data with finite arrays where the parameter of the geometric distribution is a random process. It is certainly a faster and easier algorithm to implement than the one in the original post.
Now we can optimize the worst case by introducing an opposite function which goes into opposite direction, with decreasing index from last to first and searching for a $f(j \ge i) < i$ each time.
Count the number of permutation lookups of both functions without swapping. Then choose the function with less required lookups to do the job with swapping. You can count in parallel or interleaved (assume a fair share of time so that the slower function does not get most of the time) and interrupt the counting of the slower function when it exceeds the returned count of the faster one. This case, we avoid degenerate cases and probably get a solid average case complexity as worst case (I conjecture). If this is true it would only take 3 times the average complexity of the initial algorithm which is better than square complexity in time and is guaranteed to have constant space complexity since no copies are created and swaps are inplace.
Option 2
I found an inplace-algorithm with assumed (measured) worst case $\mathcal{O}(N·log2(N))$. I thought about avoiding unnecessary visits of permutation entries and noticed that the relation between the index and its permutation entry and is already some kind of binary flag property. Python-Code:
def compute_permutation(array, pi):
for i in range(len(array)):
if (j := pi[i]) > i:
array[i], array[j] = array[j], array[i]
for i in range(len(array)-1,0, -1):
if (j := pi[i]) < i:
while pi[j] > j or j > i:
j = pi[j]
array[i], array[j] = array[j], array[i]
The algorithm yet allows for some further optimizations like avoiding walking through the full cycle for the first permutation entry which points back. I wonder, if walking through the cycles a logarithmic number of times is actually necessary when there are only few array elements left at position < i.
Option 3
For a special case with mutable permutation, if destroying the permutation is not minded, then you can do this (Python):
def compute_permutation(array, pi):
for i in range(len(array)):
j = i
while i != (k := pi[i]):
array[j], array[k] = array[k], array[j]
pi[i], pi[k] = pi[k], pi[i]
j = k
Does not allocate additional memory besides local variables and has $\mathcal{O}(N)$ time complexity and $\mathcal{O}(1)$ space complexity. The trick is to exploit the permutation as buffer which turns it into a linear range of indices at the end. This is probably not worse than the compression options found in the answer of Chad Brewbaker which also destroys the original value of the permutation entries.
Option 4
If there is a way to extract the original index from a given array-element in $\mathcal{O}(1)$ steps and space via a function index_of() then you can do even better without modifying the permutation function but same complexity lower bounds. Just use the comparison of that element index against the permutation entry as a flag:
def compute_permutation(array, pi):
for i in range(len(array)):
if array[i].index_of() != pi[i]:
j = i
while i != (k := pi[j]):
array[j], array[k] = array[k], array[j]
j = k
Option 5
If there is no way to extract the original index of a value in $\mathcal{O}(1)$ time then there is still a way that will always work in practice, even though some could consider it cheating. You can use signed indices and use the sign bit as a flag that is cleared at the end of the algorithm. Set the flag for permutation entries whose corresponding element was already swapped to the correct position. This is always feasible in practice, at least in Java which always reserves a sign bit for integer values even though it is useless for indices.
void compute_permutation(Object[] array, int[] pi)
{
for(int i=0; i<array.length; i++)
{
if (pi[i] >= 0)
{
for(int j=i, k; i != (k = pi[j]); j = k)
{
Object tmp = array[j];
array[j] = array[k];
array[k] = tmp;
pi[j] = ~pi[j];
}
}
}
for(int i=0; i<pi.length; i++) pi[i] = ~pi[i];
}
This allows for practical inplace solutions with $\mathcal{O}(N)$ overhead and no additional allocation. Only restriction: requires a writable permutation array.
Big disadvantage: any modification to the permutation entries is not thread-safe! Would require permutation copies for nested or concurrent calls with the same permutation.
Instead of modifying permutation entries, modifying the array elements with a flag would be more useful. Low-Level languages often have access to reference values (addresses) where an unused bit can be set as a flag and later removed. Non-negative integer values could use the sign as flag as well (in Java). Since the input array needs to be modified anyways with an inplace algorithm, it would not cause additional problems.
