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

c++ arrays
Edit
Report