<p>It is possible, people calling it homework probably haven't tried solving it yet.</p>

<p>We use the following as a sub-routine:</p>

<pre><code>Given an array a1 a2 ... an b1 b2 .. bn, convert in O(n) time and O(1) space to

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

<p>A solution for that can be found here: <a href="http://arxiv.org/abs/0805.1598" rel="noreferrer">http://arxiv.org/abs/0805.1598</a></p>

<p>We use that as follows.</p>

<p>Do the above interleaving for the first 2^(k+1) - 2 elements, starting at k=1 repeating for k=2, 3 etc, till you go past the end of array.</p>

<p>For example in your array we get (interleaving sets identified by brackets)</p>

<pre><code> 8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15   
[ ][ ]

 4, 8, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15   (k = 1, interleave 2)
[        ][        ]  

 2, 4, 6, 8, 10, 12, 14, 1, 3, 5, 7, 9, 11, 13, 15   (k = 2, interleave 6)
[                      ][                     ]

 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15   (k = 3, interleave 14)
</code></pre>

<p>So the total time is n + n/2 + n/4 + ... = O(n).
Space used is O(1).</p>

<p>That this works can be proved by induction.</p>
Sort BST in O(n) using constant memory
<p>This is not a homework. Just an interesting task :)</p>

<p>Given a complete binary search three represensted by array. Sort the array in O(n) using constant memory.</p>

<p>Example:</p>

<p>Tree:</p>

<pre><code>              8
           /     \
          4       12
         /\       / \
        2  6     10  14
       /\  /\    /\   /\
      1 3 5  7  9 11 13 15
</code></pre>

<p>Array: 8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15</p>

<p>Output: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15</p>