Array-Bewegung von a1, .., an, b1, .., bn zu a1, b1, .., an, bn

Heute bin ich auf eine Frage gestoßen, die mich wirklich verwundert

Frage

Ich habe Array wie folgt:arr[a1, a2, a3....an, b1, b2, b3.....bn], wie man die Elemente des Arrays verschiebt, um sie zu übertragenarr[a1, b1, a2, b2......an,bn]Und Sie sollten die Bewegung an Ort und Stelle tun?space complexity should be constant）.

Ich habe mein Bestes versucht, um es zu überdenken und einen hässlichen Algorithmus zu erhalten, genau wie bei der Blasensortierung:

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

Aber die zeitliche Komplexität ist O (n2), wer kann mir einen besseren Algorithmus geben? Ich finde eine andere bessere Methode wie 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)

Hier sind ganze 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);
}