In-place array reordering?

With mutating indices :(. Without looks hard (see stable in-place mergesort).

a = [8, 6, 7, 5, 3, 0, 9]indices = [3, 6, 2, 4, 0, 1, 5]for i in xrange(len(a)):    x = a[i]    j = i    while True:        k = indices[j]        indices[j] = j        if k == i:            break        a[j] = a[k]        j = k    a[j] = xprint a

This is what I call a "permute from" algorithm. In C-like language it would look as follows

  for (i_dst_first = 0; i_dst_first < n; ++i_dst_first)  {    /* Check if this element needs to be permuted */    i_src = indices[i_dst_first];    assert(i_src < n);    if (i_src == i_dst_first)      /* This element is already in place */      continue;    i_dst = i_dst_first;    pending = a[i_dst];    /* Follow the permutation cycle */    do    {      a[i_dst] = a[i_src];      indices[i_dst] = i_dst;      i_dst = i_src;      i_src = indices[i_src];      assert(i_src != i_dst);    } while (i_src != i_dst_first);    a[i_dst] = pending;    indices[i_dst] = i_dst;  }

Note though that this algorithm destroys the index array. I call it "permute from" since the index[i] value specifies from where to take the i-th element of the resultant sequence.

Note also, that the number of "element move" operations required for in-place permutation of a sequence is equal to number of misplaced elements + number of cycles in the permutation. This algorithm achieves this limit, so in terms of the number of moves no better algorithm is possible.

Potential problem with this algorithm is that it is based on "juggling" approach, making its cache behavior far from optimal. So, while this algorithm is the best one in theory, it could lose to some more "practical" algorithms in real life.

One can also implement a "permute to" algorithm, where index[i] value specifies where to relocate the original i-th element.

If a is an array of integers, then an O(n)-time, O(1)-space algorithm is possible that keeps the order of permutation indices. In this case we can permute a into indexes and use a as a temporary storage of the inverse permutation. After the permutation is performed, the arrays a and indices are swapped, and indices is inverted in situ using e.g. algorithm J from TAoCP. The following is a working Java program:

int [] a = {8, 6, 7, 5, 3, 0, 9};int [] indices = {3, 6, 2, 4, 0, 1, 5};int n = indices.length;int i, j, m;    // permute a and store in indices// store inverse permutation in a for (j = 0; j < n; ++j) {     i = indices[j]; indices[j] = a[i]; a[i] = j; } // swap a and indices for (j = 0; j < n; ++j) {     i = indices[j]; indices[j] = a[j]; a[j] = i; } // inverse indices permutation to get the original for (i = 0; i < n; ++i) {indices[i] = -indices[i] - 1;} for (m = n - 1; m >= 0; --m) {     // for (i = m, j = indices[m]; j >= 0; i = j, j = indices[j]) ;     i = m; j = indices[m];      while (j >= 0) {i = j; j = indices[j];}     indices[i] = indices[-j - 1];     indices[-j - 1] = m;}