今天，我遇到了一个让我很困惑的问题

题

我有数组，就像：arr[a1, a2, a3....an, b1, b2, b3.....bn]，如何移动数组的元素以将其转移到中arr[a1, b1, a2, b2......an,bn]，然后就地进行移动（space complexity should be constant）。

我尽力考虑一下，并得到一个像冒泡排序这样的丑陋算法：

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

但是时间复杂度是O（n 2），谁能给我一个更好的算法？我找到了另一个更好的方法，就像快速排序：

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)

这是完整的代码：

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);
}