Sort an almost complete binary search tree array.

Almost complete binary trees can be represented compactly using arrays, where the children of $a[i]$ are $a[2i]$ and $a[2i+1]$, with the root being $a[1]$ (assume index of the array starts at 1 for this problem).

Given an almost complete binary search represented in such a manner: i.e. given the array $A$ representing the tree, can you give an $O(n)$ time and $O(1)$ space algorithm (WORD RAM model) which will sort the array?


For example if the tree is [image swiped from someone's webpage in cmu]

the corresponding array would be

$$[10, 6, 18, 4, 8, 15, 21]$$

and your algorithm needs to sort it so that it becomes

$$[4, 6, 8, 10, 15, 18, 21]$$

 [I have labelled this hard, because the solution I have uses a result which is hard. Hint: You can find that result on this blog]

[Solution]