Perfect shuffle algorithm 完美洗牌算法

https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/en/35.0.md
There is an array of length 2n {a1, a2, a3, ..., an, b1, b2, b3, ..., bn}, hope to be {a1, b1, a2, b2, ...., an, bn} after be sorted.Consider is there any solution with the time complexity of o(n) and space complexity of 0(1).

Divide and conquer algorithm perfect_shuffle2

//Time complexity O (n), space complexity O (1) and array index starts at 1
void perfect_shuffle2(int *a, int n)
{
    int t, i;
    if (n == 1)
    {
        t = a[1];
        a[1] = a[2];
        a[2] = t;
        return;
    }
    int n2 = n * 2, n3 = n / 2;
    if (n % 2 == 1)    //for the odd case
    {
        t = a[n];
        for (i = n + 1; i <= n2; ++i)
        {
            a[i - 1] = a[i];
        }
        a[n2] = t;
        --n;
    }
    //the even case below

    for (i = n3 + 1; i <= n; ++i)
    {
        t = a[i];
        a[i] = a[i + n3];
        a[i + n3] = t;
    }

    // [1.. n /2]
    perfect_shuffle2(a, n3);
    perfect_shuffle2(a + n, n3);
}

http://rosettacode.org/wiki/Perfect_shuffle

完美洗牌算法
有个长度为2n的数组{a1,a2,a3,...,an,b1,b2,b3,...,bn}，希望排序后{a1,b1,a2,b2,....,an,bn}，请考虑有无时间复杂度o(n)，空间复杂度0(1)的解法。

void PefectShuffle1(int *a, int n)
{
    int n2 = n * 2, i, b[N];
    for (i = 1; i <= n2; ++i)
    {
        b[(i * 2) % (n2 + 1)] = a[i];
    }
    for (i = 1; i <= n2; ++i)
    {
        a[i] = b[i];
    }
}

2.2.1、走圈算法cycle_leader

http://arxiv.org/pdf/0805.1598.pdf

Read full article from 完美洗牌算法