Array movement from a1,..,an,b1,..,bn to a1,b1,..,an,bn

Question

Today, I met a question which is really puzzled me

Question

I have array just like:arr[a1, a2, a3....an, b1, b2, b3.....bn], how to move the elements of the array to transfer it into arr[a1, b1, a2, b2......an,bn], And you should do the movement in-place（space complexity should be constant）.

I tried my best to think it over and get an ugly algorithm just like bubble-sort:

b1 moves forward by n - 1;
b2 moves forward by n - 2;
.
.
bn-1 moves forward by 1;

But the time complexity is O(n²), who can give me a better algorithm? I find another better method just like quick-Sort:

First we swap the element from a(n/2) to a(n) with the elements from b1 to b(n/2);now we get two independent sub problems,So we can solve it by recursion.
T(n) = 2T(n/2) + O(n) 
the time complexity is O(nlgn)

here are whole codes:

void swapArray(int *arr, int left, int right)
{
    int mid = (left + right) >> 1;
    int temp = mid + 1;
    while(left <= mid)
    {
        swap(arr[left++], arr[temp++]);
    }
}
void arrayMove(int *arr, int lb, int le, int rb, int re)
{
    if(le - lb <= 0 || re - rb <= 0)
        return;
    int mid = (lb + le + 1) >> 1;
    int len = le - mid;
    if(rb + len >= re)
    {
        swapArray(arr, mid + 1, rb);
    }
    else
    {
        swapArray(arr, mid, rb + len);
    }
    arrayMove(arr, lb, mid - 1, mid, le);
    arrayMove(arr, rb, rb + len, rb + 1 + len, re);
}

Answer 1

After dabbling and experimenting/stumbling a little, I think I'm beginning to understand, although the math is still hard for me. I think it goes something like this:

Determine the permutation cycles of the transposition (this can be done during or before the actual data transfer). The formula, to = 2*from mod (M*N - 1), where M = 2, N = array length / 2, can be used to find the index destinations (permutation). (I reduced the formula for this question since we know M = 2.) A marker of visited indexes can help determine the start of the next cycle (technically speaking, one could use the cycle calculations rather than a bitset as a marker, keeping only the next cycle-start in memory). A temporary variable holds the data from the start address until the cycle-end.

Altogether, that could mean two temporary variables, the cycle calculations, and one move in-place per array element.

For example:

arr          = 0,1,2,3,4,5,6,7,8,9
destinations:  0,2,4,6,8,1,3,5,7,9

start = 1, tmp = arr[1]    

cycle start
5->1, 7->5, 8->7, 4->8, 2->4, tmp->2
cycle end

not visited - 3

start = 3, tmp = arr[3]

cycle start
6->3, tmp->6
cycle end

Transposition complete.

Any questions?
Feel free to ask and please visit http://en.wikipedia.org/wiki/In-place_matrix_transposition