Sort binary tree array [Solution]

The problem was to sort an almost complete binary search tree, which is represented as an array: the children of $a[i]$ are $a[2i]$ and $a[2i+1]$.

The catch was to sort in $O(n)$ time and using $O(1)$ space.

[Detailed problem statement is here]

Solution

---

The solution depends on the following

1) If $a[1], a[2], \dots, a[2^k-1]$ is already sorted, then we can sort $a[1], a[2], \dots, a[2^{k+1}-1]$ by interleaving $$\{a[1], a[2], \dots, a[2^k-1]\}\quad \{a[2^k], a[2^k+1], \dots, a[2^{k+1}-1]\}$$ as

$$a[2^k], a[1], a[2^k+1], a[2], \dots, a[2^{k+1} -2], a[2^k-1], a[2^{k+1}-1]$$

Now this interleaving can be done on linear time and constant space, using the solution in the blog post here: http://ruffnsluff.blogspot.com/2015/01/solution-to-rearrange-array-algorithm.html


So starting with $k=1$ and so on, we can do this in time  $n + n/2 + n/4 + \dots$ = $O(n)$ and $O(1)$ space.


[Sorry for the terse solution, I suggest you try it out with a few examples].