De-interleave an array in place?

Question

Lets say I have an array of interlaced data, such as 1a2b3c4d5e, and I want to de-interlace it into an array that looks like 12345abcde, in place (without a temporary buffer). What would be the fastest way of doing this?

What I have so far is this

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

  int i = 1;
  for(i = 1; i*2<length; i++){
    //swap i with i*2
    T temp = arr[i];
    arr[i] = arr[i*2];
    arr[i*2] = temp;
  }
  deinterlace(arr+i, length-i);
}

which unfortunately doesn't work with arrays not a power of 2 in size

edit: this algo fails at larger powers of 2 anyway so I guess I'm at square 0 again

edit 2: I have found an nlogn algorithm for this, given either an O(n) array rotate function, or an initial size which is a power of 2

works like so:

1a2b3c4d5e6f7g, "chunk size" = 1 initial,

split into groups of chunk size *4 1a2b 3c4d 5e6f 7g

swap the inner 2 chunks of each group 12ab 34cd 56ef 7g

repeat with chunk size = chunk size *2

12ab34cd 56ef7g (read: 56 ef 7 g) -> 1234abcd 567efg

1234abcd567efg -> 1234567abcdefg

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

  for(int i = 0; i<length; i+=group_ct*4){
    int rot_count = group_ct;

    int i1 = i + group_ct;
    int i2 = i+group_ct*4 - group_ct;

    if(i2+group_ct > length){
      i2 = i1 + (length-i1)/2+group_ct/2;
    }

    rotate(arr, i1, i2, group_ct);

  }

  deinterlace(arr, length, group_ct * 2);
}

edit 3 I guess the correct term is deinterleave, not deinterlace

Answer 1

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.