<p>This is the so called in-place in-shuffle algorithm, and it's an extremely hard task if you want to do it efficiently. I'm just posting this entry so people don't post their so called "solutions" claiming that it can be extended to work with O(1) space, without any proof...</p>

<p>Here is a paper for a simpler case when the list is in the form: <code>a1 a2 a3 ... an b1 b2 b3 .. bn</code>:</p>

<p><a href="http://arxiv.org/PS_cache/arxiv/pdf/0805/0805.1598v1.pdf">http://arxiv.org/PS_cache/arxiv/pdf/0805/0805.1598v1.pdf</a></p>
Interview test - rearrange the array
<blockquote>
  <p><strong>Possible Duplicate:</strong><br>
  <a href="https://stackoverflow.com/questions/5557326/reordering-of-array-elements">Reordering of array elements</a>  </p>
</blockquote>



<p>In given array of elements like [a1,a2,a3,..an,b1,b2,b3,..bn,c1,c2,c3,...cn] Write a program to merge them like [a1,b1,c1,a2,b2,c2,...an,bn,cn].
We have to do it in O(1) extra space.</p>

<p>Sample Testcases:</p>

<pre><code>Input #00:

{1,2,3,4,5,6,7,8,9,10,11,12}

Output #00:

{1,5,9,2,6,10,3,7,11,4,8,12}

Explanation:

Here as you can notice, the array is of the form
{a1,a2,a3,a4,b1,b2,b3,b4,c1,c2,c3,c4} 
</code></pre>

<p>EDIT:
I got it in Amazon placement test. Have been trying it for a long time.
PLease provide psuedo code. What i tried is finding new position p for second element e(1st is already at correct position), inserting e at p and repeating the same for the old element at position p. But this is ending in a cycle.
I tried detecting cycle and incrementing the starting position by 1. But even this is not working.</p>

<p>EDIT2: </p>

<pre><code>#include &lt;iostream&gt;
using namespace std;

int pos(int i, int n) 
{
    if(i&lt;n)  
     {
         return  3*i;

           }

       else if(i&gt;=n &amp;&amp; i&lt;2*n)
       {

            return 3*(i-n) + 1;
            }
    else if(i&gt;=2*n &amp;&amp; i&lt;3*n)
       {
            return 3*(i-2*n) + 2;
            }
return -1;
}
void printn(int* A, int n)
{
         for(int i=0;i&lt;3*n;i++)  
             cout &lt;&lt; A[i]&lt;&lt;";";

    cout &lt;&lt; endl;
     }

void merge(int A[], int n)
{
 int j=1;    
 int k =-1;
 int oldAj = A[1];
 int count = 0;
 int temp;
 while(count&lt;3*n-1){

 printn(A,n);
 k = pos(j,n);
 temp = A[k];
 A[k] = oldAj;
 oldAj = temp;
 j = k;
 count++;
 if(j==1) {j++;}
}

 }

int main()
{
    int A[21] = {1,4,7,10,13,16,19,2,5,8,11,14,17,20,3,6,9,12,15,18,21};
    merge(A,7);

    cin.get();}
</code></pre>