Is it possible to rearrange an array with constant memory overhead?

Question

I stumbled upon this while reading some StackOverflow questions but could not find a satisfying answer.

Suppose we have an array A of length n containing its indexes from 0 to n-1 in a random fashion. Is it possible to rearrange the array so that its outcome is A[ A[i] ] with constant O(1) memory overhead?

Example:

A = [ 3, 2, 0, 1 ]
rearrange( A )
A = [ 1, 0, 3, 2 ]

If it is possible an outline of the algorithm would be nice. Otherwise an explanation why it is not possible. Since inplace sorting is a thing maybe this works similar.

Clarification: If you do not have the memory constraint the algorithm is trivial:

A = [ 3, 2, 0, 1 ]
A_r = Array_of_size( A )
for i = 0 to Arraysize - 1
   A_r[ i ] = A[ A[i] ]

Outcome A_r = [ 1, 0, 3, 2]

Answer 1

It is possible.

The input array consists of values that are indexes in the same array, and so it is a collection of one or more cycles. Each cycle can have 1 or more elements.

The mutation of the array can best be performed cycle by cycle, as the change in one cycle would only require a temporary storage of one value in that cycle, while the "next" value is copied into the "previous" slot until the whole cycle has been visited and the temporary value can be put in the last slot.

One of the things to consider is that after a cycle has mutated like that, it might not result in a cycle of the same length. For instance, if a cycle has length 4, then the mutation will result in 2 cycles of 2 values. More generally, a cycle with even length will divide into two cycles. Odd cycles keep their length, and just have their order changed.

Once a cycle has mutated, the algorithm should never revisit any of its values "accidentally" applying the mutation to that cycle again.

One way to ensure that this does not happen is to only apply the mutation to a cycle when its rightmost element is visited in a left-to-right iteration. This is the key of the proposed algorithm. That way one can be sure that the elements in this cycle will never be visited again, and will not be mutated again.

Here is an implementation in JavaScript. You can enter the array values in an input field. The algorithm is executed at every change to the input:

function arrange(a) {
    function isRightmostOfCycle(i) {
        let j = a[i]
        while (j < i) j = a[j]
        return j == i
    }

    function updateCycle(i) {
        let saved = a[i]
        let k = i
        for (let j = a[i]; j < i; j = a[j]) {
            a[k] = a[j]
            k = j
        }
        a[k] = saved
    }

    for (let i = 0; i < a.length; i++) {
        if (isRightmostOfCycle(i)) updateCycle(i)
    }
    return a
}

// I/O handling
let input = document.querySelector("input")
let output = document.querySelector("pre");
(input.oninput = function () {
    let a = (input.value.match(/\d+/g) || []).map(Number)
    // Check whether input is valid
    let i = a.findIndex((_,i) => !a.includes(i))
    output.textContent = i < 0 ? arrange(a) : "Missing " + i
})();

input { width: 100% }

Array values: <input value="2,0,5,7,6,4,1,8,3"><p>
Result: 
<pre></pre>

The check whether an index represents the rightmost element of a cycle has a time complexity of O(n), so the total time complexity is O(n²). The additional space complexity however is constant.