这是不是一门功课。只是一个有趣的任务：）
This is not a homework. Just an interesting task :)
鉴于阵列psensted一个完整的二进制搜索3重$ P $。排序使用常量内存在O（n）的阵列。
Given a complete binary search three represensted by array. Sort the array in O(n) using constant memory.
例如：
树：
8 / \ 4 12 /\ / \ 2 6 10 14 /\ /\ /\ /\ 1 3 5 7 9 11 13 15
阵列：8,4，12，2，6，10，14，1，3，5，7，9，11，13，15
Array: 8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15
输出：1，2，3，4，5，6，7，8，9，10，11，12，13，14，15
Output: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
推荐答案这是可能的，人们称之为功课大概还没有尝试解决它。
It is possible, people calling it homework probably haven't tried solving it yet.
我们使用以下作为子例程：
We use the following as a sub-routine:
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有一个解决方案可以在这里找到： arxiv/abs/0805.1598
A solution for that can be found here: arxiv/abs/0805.1598
我们使用如下：
执行上面交错的第2 ^（K + 1） - 2个元素，开始在k = 1的重复对于k = 2，3等，直到你走过去的数组的末尾
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.
例如您的阵列中，我们得到（交错确定括号套）
For example in your array we get (interleaving sets identified by brackets)
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)
所以，总时间为N + N / 2 + N / 4 + ...... = O（N）。 使用空间是O（1）。
So the total time is n + n/2 + n/4 + ... = O(n). Space used is O(1).
这本著作可以通过归纳证明。
That this works can be proved by induction.