<ol>
<li>Get largest sub-array having size 3<sup>k</sup>+1</li>
<li>Apply cycle leader algorithm to the parts of this sub-array, starting from positions 1, 3, 9, ... 3<sup>k-1</sup>: move element to its proper position in sub-array (even-indexed elements to the left of sub-array, odd-indexed - to the right), the replaced element should be also moved to its proper position, etc. until this procedure comes back to the starting position. <a href="http://arxiv.org/abs/0805.1598" rel="nofollow">This paper</a> gives number-theoretic explanation why such selection of starting positions shuffles sub-array to the correct order.</li>
<li>Process the remaining parts of the array recursively, using steps 1 and 2.</li>
<li>Now we only need to join the reordered parts together. Start with the smaller sub-arrays at the end of the whole array. To exchange sub-array halves, use reverse algorithm: reverse(reverse(a), reverse(b)); or, for sub-array halves of equal size, use pair-wise swaps.</li>
<li>Now all even-positioned elements are on the left. To get them on the right, as required, exchange elements i and i+N/2 for all i = 0 .. N/2-1.</li>
</ol>

<p>Algorithm is in-place, time complexity is O(N).</p>

<p>Example:</p>

<pre><code>0 1 2 3 4  5 6 7 8 9   10 11 (the original array)
0 1 2 3 4  5 6 7 8 9 # 10 11 (split to sub-arrays)
0 2 4 3 8  1 6 5 7 9 # 10 11 (first cycle leader iteration, starting with 1)
0 2 4 6 8  1 3 5 7 9 # 10 11 (second cycle leader iteration, starting with 3)
0 2 4 6 8  9 7 5 3 1 # 10 11(2nd half of 1st part&amp; 1st half of 2nd part reversed)
0 2 4 6 8 10 1 3 5 7    9 11 (both halves reversed together)
</code></pre>

<p>Variation of this algorithm, that does not need step 5:</p>

<ul>
<li>On step 1, get largest sub-array having size 3<sup>k</sup>-1.</li>
<li>On step 2, move even-indexed elements to the right of sub-array, odd-indexed - to the left. Use starting positions 0, 2, 8, ... 3<sup>k-1</sup>-1 for cycle-leader algorithm.</li>
</ul>

<p>Here is different O(N log N) in-place algorithm, which does not need number-theoretic proofs:</p>

<ol>
<li>Reinterpret your array as a sequence of single-element 2*2 matrices, transpose these matrices.</li>
<li>Reinterpret the result as a sequence of two-element 2*2 matrices and transpose them.</li>
<li>Continue while matrices size is less than the array size.</li>
<li>Now we only need to join the reordered parts together (exactly as in previous algorithm).</li>
<li>Exchange elements of left and right halves of the array (exactly as in previous algorithm).</li>
</ol>

<p>Example:</p>

<pre><code>0  1   2 3   4 5   6 7  (the original array)
[0 2] [1 3] [4 6] [5 7] (first transposition)
[0 2] [4 6] [1 3] [5 7] (second transposition)
</code></pre>

<p>This problem is just a special case of the <a href="http://en.wikipedia.org/wiki/In-place_matrix_transposition" rel="nofollow">In-place matrix transposition</a>.</p>
Move all odd positioned element to left half and even positioned to right half in-place
<p>Given an array with positive and negative integers, move all the odd indexed elements to the left and even indexed elements to the right.</p>

<p>The difficult part of the problem is to do it in-place while maintaining the order.</p>

<p>e.g.</p>

<pre><code>7, 5, 6, 3, 8, 4, 2, 1
</code></pre>

<p>The output should be: </p>

<pre><code>5, 3, 4, 1, 7, 6, 8, 2
</code></pre>

<p>If the order didn't matter, we could have been used partition() algorithm of quick sort.</p>

<p>How to do it in O( N )?</p>