<p>Since David does not seem interested in writing it down (well obviously he <em>is</em> interested, see the other answer :), I will use <a href="http://arxiv.org/pdf/0805.1598v1.pdf" rel="nofollow">his reference</a> to arrive at an algorithm for the case with 3 partitions.</p>

<p>First note that if we can solve the problem efficiently for some <em>m &lt; n</em> using an algorithm <em>A</em>, we can rearrange the array so that we can apply <em>A</em> and are then left with a smaller subproblem. Say the original array is</p>

<pre><code>x1 .. xm x{m+1}.. xn y1 .. ym y{m+1} .. yn z1 .. zm z{m+1} .. zn
</code></pre>

<p>We want to rearrange it to</p>

<pre><code>x1 .. xm y1 .. ym z1 .. zm x{m+1} .. xn y{m+1} .. yn z{m+1} .. zn
</code></pre>

<p>This is basically a transformation of the pattern <code>AaBbCc</code> to <code>ABCabc</code> where A, B, C and a, b, c have the same lengths, respectively. We can achieve that through a series of reversals. Let X' denote the reversal of string X here:</p>

<pre><code>   AaBbCc
-&gt; Aa(BbCc)' = Aac'C'b'B'
-&gt; Aac'(C'b')'B' = Aac'bCB'
-&gt; A(ac'bCB')' = ABC'b'ca'
-&gt; ABCb'ca'
-&gt; ABC(b'ca')' = ABCac'b
-&gt; ABCa(c'b)' = ABCab'c
-&gt; ABCabc
</code></pre>

<p>There's probably a shorter way, but this is still just a constant number of operations, so it takes only linear time. One could use a more sophisticated algorithm here to implement some of the cyclic shifts, but that's just an optimization.</p>

<p>Now we can solve the two partitions of our array recursively and we're done.</p>

<p>The question remains, what would be a nice m that allows us to solve the left part easily?</p>

<p>To figure this out, we need to realize that what we want to implement is a particular <a href="http://en.wikipedia.org/wiki/Permutation" rel="nofollow">permutation</a> P of the array indices. Every permutation <a href="http://en.wikipedia.org/wiki/Permutation#Cycle_notation" rel="nofollow">can be decomposed into a set of cycles</a> <code>a0 -&gt; a1 -&gt; ... -&gt; a{k-1} -&gt; a0</code>, for which we have P(ai) = a{(i + 1) % k}. It is easy to process such a cycle in-place, the algorithm is outlined <a href="http://en.wikipedia.org/wiki/In-place_matrix_transposition#Non-square_matrices%3a_Following_the_cycles" rel="nofollow">on Wikipedia</a>. </p>

<p>Now the problem is that after you completed processing one of the cycle, to find an element that is part of a cycle you have not yet processed. There is no generic solution for this, but for some particular permutations there are nice formulas that describe what exactly the positions are that are part of the different cycles. </p>

<p>For your problems, you just choose m = (5^(2k) - 1)/3, such that m &lt; n and k is maximum. A sequence of elements that are part of all the different cycles is 5^0, 5^1, ..., 5^{k-1}. You can use those to implement the cycle-leader algorithm on the left part of the array (after the shifting) in O(m).</p>

<p>We solve the leftover right part recursively and get an algorithm to solve the problem in time</p>

<pre><code>T(n) = O(m) + T(n - m)
</code></pre>

<p>and since m >= Omega(n), we get T(n) = O(n).</p>
Interleave three equally sized partitions in an array inplace in O(n) time
<p>Given an array of size 3n of the form</p>

<pre><code>[x1, x2, x3... xn, y1, y2, y3... yn, z1, z2, z3... zn]
</code></pre>

<p>Convert it to <code>[x1, y1, z1, x2, y2, z2, ... xn, yn, zn]</code></p>

<p>Here xn, yn, zn can be any integers. See example input and output below.</p>

<p>Two constraints</p>

<ol>
<li>Do in O(n)</li>
<li>O(1) memory (inplace)</li>
</ol>

<p>An example input and output are as follows.</p>

<p><strong>Input :</strong><br>
<code>[5, 8, 11, 3, 2, 17, 21, 1, 9]</code> 3n = 9. So n = 3.</p>

<p>Here
<code>x1=5 x2=8 x3=11 y1=3 y2=2 y3=17 z1=21 z2=1 z3=9</code></p>

<p><strong>Output :</strong><br>
<code>[5, 3, 21, 8, 2, 1, 11, 17, 9]</code></p>

<p><strong>One possible O(n log n) soln:</strong> 
Considering just x's and y's. Now I can swap all y's to its position which will leave me x2, x4, x6 swapped out of position. Then I will swap in x2, x4's which will leave x3, x7's out of position. And next iteration would be x8, x16's. This would take me to O(n log n) but not O(n).</p>