<p>Assuming you mean O(1) memory (or depending on the model O(log n)) rather than <em>no extra memory</em>, a linear time in-place algorithm exists.</p>

<p>This paper: <a href="http://arxiv.org/abs/0805.1598" rel="nofollow">http://arxiv.org/abs/0805.1598</a> has an algorithm for the case when you have</p>

<p><code>a1 ... an b1 ... bn</code> and want to convert to </p>

<p><code>b1 a1 b2 a2 ... bn an</code>.</p>

<p>The paper also mentions that you can generalize this to other k-way shuffles. In your case, k = 3.</p>

<p>The algorithm in the paper will give the following:</p>

<p>Start with <code>a1 a2 ... an b1 b2 ... bn c1 c2 ... cn</code> and convert to</p>

<p><code>c1 b1 a1 c2 b2 a2 ... cn bn an</code></p>

<p>Another pass through this, and you can easily get <code>a1 b1 c2 a2 b2 c2 ... an bn cn</code>.</p>

<p>Now to generalize the algorithm in the paper, we need to pick a prime p, such that k is a primitive root of p^2.</p>

<p>For k = 3, p = 5 will do.</p>

<p>Now to apply the algorithm, first you need to find the largest m &lt; n such 3m+1 is a power of 5.</p>

<p>Note: this will only happen when 3m+1 is an <em>even</em> power of 5. Thus you can actually work with powers of 25 when trying to find the m. (5^odd - 1 is not divisible by 3).</p>

<p>Once you find m,</p>

<p>You shuffle the array to be</p>

<p><code>[a1 a2 ... am b1 b2 ... bm c1 c2 ... cm] [a(m+1) ... an b(m+1) ... bn c(m+1) ... cn]</code></p>

<p>and then use the follow the cycle method(refer the paper) for the first 3m elements, using the powers of 5 (including 1 = 5^0) as the starting points of the different cycles) and do a tail recursion for the rest.</p>

<p>Now to convert
<code>a1 a2 ... an b1 b2 ... bn c1 c2 ... cn</code></p>

<p>to </p>

<p><code>[a1 a2 ... am b1 b2 ... bm c1 c2 ... cm] [a(m+1) ... an b(m+1) ... bn c(m+1) ... cn]</code></p>

<p>you first do a cyclic shift to get</p>

<p><code>a1 a2 ... am [b1 b2  bm a(m+1) .. an] b(m+1) .. bn c1 c2 ... cn</code></p>

<p>(the elements in the square brackets are the ones that were shifted)</p>

<p>Then do a cyclic shift to get</p>

<p><code>a1 a2 ... am b1 b2  bm a(m+1) .. an [c1 c2 ..cm b(m+1) .. bn ] c(m+1) ... cn</code></p>

<p>And then a final shift to </p>

<p><code>a1 a2 ... am b1 b2  bm [c1 c2 ..cm a(m+1) .. an ] b(m+1) .. bn  c(m+1) ... cn</code></p>

<p>Note that cyclic shift can be done in O(n) time and O(1) space.</p>

<p>So whole algorithm is O(n) time and O(1) space.</p>
Reordering of array elements
<p>Given an array </p>

<pre><code>[a1 a2 a3 ... an b1 b2 b3 ... bn c1 c2 c3 ...cn]
</code></pre>

<p>without using extra memory how do you reorder into an array</p>

<pre><code>[a1 b1 c1 a2 b2 c2 a3 b3 c3 ... an bn cn]
</code></pre>