De-interleave an array in place?

Your original idea will almost work for an in-place deinterleave. You just need to account for the fact that when you swap an item into place, you displace the item that the formula expects to find there.

So first, define the source_index function: given a perfectly interleaved array of length N and an index i, return the item that should be in i. The first half comes from every other even item, the last half from every other odd item.

int source_index(int i, int length) {
  int mid = length-length/2;

  if (i<mid) {
    return i*2;
  }
  return (i-mid)*2+1;
}

Now you can walk through the array swapping items into place. But if you find a source index that is less than the current target index, you need to re-do the calculation to find out where it was swapped to.

template<typename T>
void deinterlace(T* arr, int length){
  if(length<=1) return;

  int i = 1;
  for(i = 1; i<length; i++){
    int j = source_index(i, length);
    while (j<i) { //walk the chain of swaps
      j = source_index(j, length);
    }
    T temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
}

This does exactly N swaps. The number of calls to source_index is somewhat chaotic, but seems to exhibit NlgN growth.

This is essentially a matrix transposition problem. Your array

[1 a]
[2 b]
[3 c]
[4 d]

is equivalent to 1, a, 2, b, 3, c, 4, d if represented as a vector (by reading rows first). The transpose of this matrix is:

[1 2 3 4]
[a b c d]

which is equivalent to 1, 2, 3, 4, a, b, c, d.

There is a wikipedia page that deals with in-place matrix transposition for the general cases. I guess, the algorithm for non-square matrix would be directly applicable.

---

There is a slow (not sure if O(n^2) or worse, and it is late) algorithm that you can use. The idea is to in place rotate the sub-array from position i to position 2*i. For example:

START: 1a2b3c4d5e6f
1(a2)...         -> 1(2a)...
12(ab3)...       -> 12(3ab)...
123(abc4)...     -> 123(4abc)...
1234(abcd5)...   -> 1234(5abcd)...
12345(abcde6)... -> 12345(6abcde)..
123456(abcdef)   -> DONE

The first member of the array is index 0. At step 1, you select the sub-array a[1:2], and rotate it right (all members go to next location, and the last one goes to start). Next step, you select a[2:4], and rotate that, etc. Make sure you don't rotate the last sub-array a[n/2:n].

---

And a final option, if you do not need to do bulk operations for performance (such as memcpy), is to provide an accessor function, and transform the index instead of moving any bytes. Such a function is almost trivial to write: if index is less than max/2, return entry at 2*index, otherwise, return entry at 2*(index-max/2)+1.