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.

Answer 2

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.

Answer 3

If you don't care about the order of the resultant array, the fastest way I can think of is to do successive swaps using a 'head' and 'tail' index.

int head = 1;
int tail = length - 2;
while (head < tail)
{
    T temp = arr[head];
    temp = arr[head];
    arr[head] = arr[tail];
    arr[tail] = temp;
    head += 2;
    tail -= 2;
}

For your example case, the result would be 15243cbdae after 2 iterations.