<p>It's called <a href="http://en.wikipedia.org/wiki/In_shuffle" rel="nofollow">in-place in-shuffle problem</a>. Here is its implementation in C++ based on <a href="http://arxiv.org/abs/0805.1598" rel="nofollow">here</a>.</p>

<pre><code>void in_place_in_shuffle(int arr[], int length)
{
    assert(arr &amp;&amp; length&gt;0 &amp;&amp; !(length&amp;1));

    // shuffle to {5, 0, 6, 1, 7, 2, 8, 3, 9, 4}
    int i,startPos=0;
    while(startPos&lt;length)
    {
        i=_LookUp(length-startPos);
        _ShiftN(&amp;arr[startPos+(i-1)/2],(length-startPos)/2,(i-1)/2);
        _PerfectShuffle(&amp;arr[startPos],i-1);
        startPos+=(i-1);
    }

    // local swap to {0, 5, 1, 6, 2, 7, 3, 8, 4, 9}
    for (int i=0; i&lt;length; i+=2)
        swap(arr[i], arr[i+1]);
}

// cycle
void _Cycle(int Data[],int Lenth,int Start)
{
    int Cur_index,Temp1,Temp2;

    Cur_index=(Start*2)%(Lenth+1);
    Temp1=Data[Cur_index-1];
    Data[Cur_index-1]=Data[Start-1];

    while(Cur_index!=Start)
    {
        Temp2=Data[(Cur_index*2)%(Lenth+1)-1];
        Data[(Cur_index*2)%(Lenth+1)-1]=Temp1;
        Temp1=Temp2;
        Cur_index=(Cur_index*2)%(Lenth+1);
    }
}


// loop-move array
void _Reverse(int Data[],int Len)
{
    int i,Temp;
    for(i=0;i&lt;Len/2;i++)
    {
        Temp=Data[i];
        Data[i]=Data[Len-i-1];
        Data[Len-i-1]=Temp;
    }
}

void _ShiftN(int Data[],int Len,int N)
{
    _Reverse(Data,Len-N);
    _Reverse(&amp;Data[Len-N],N);
    _Reverse(Data,Len);

}

// perfect shuffle of satisfying [Lenth=3^k-1] 
void _PerfectShuffle(int Data[],int Lenth)
{
    int i=1;

    if(Lenth==2)
    {
        i=Data[Lenth-1];
        Data[Lenth-1]=Data[Lenth-2];
        Data[Lenth-2]=i;
        return;
    }
    while(i&lt;Lenth)
    {
        _Cycle(Data,Lenth,i);
        i=i*3;
    }
}

// look for 3^k that nearnest to N
int _LookUp(int N)
{
    int i=3;
    while(i&lt;=N+1) i*=3;

    if(i&gt;3) i=i/3;

    return i;
}
</code></pre>

<hr>

<p><strong>Test:</strong></p>

<pre><code>int arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};  
int length = sizeof(arr)/sizeof(int);
in_place_in_shuffle(arr, length);
</code></pre>

<p>After this, <code>arr[]</code> will be <code>{0, 5, 1, 6, 2, 7, 3, 8, 4, 9}</code>.</p>
Interleave array in constant space
<p>Suppose we have an array
a1, a2,... , an, b1, b2, ..., bn.</p>
<p>The goal is to change this array to
a1, b1, a2, b2, ..., an, bn in O(n) time and in O(1) space.
In other words, we need a linear-time algorithm to modify the array in place, with no more than a constant amount of extra storage.</p>
<p>How can this be done?</p>