一道面试题，关于BST数组排序解决办法

一道面试题，关于BST数组排序
一棵二叉排序树BST，按层次顺序排放在数组中，
就是和Heap结构一样，数组第i个元素的两个孩子在数组2*i+1和2*i+2位置上。
如何将这个数组排序，时间O(n)，空间O(1)。
例：4   2   6   1   3   5   7
排序成1   2   3   4   5   6   7

[解决办法]
先建立一种映射关系map（原数组下标）＝排序后的位置
这种关系应该是
int map(n)
{
int mask=0x01;
int bitn=0;
int s;
while(n+1&mask==0){bitn++;mask < <=1;}
s=0x1 < <bitn;
return ((n-s) < <1+1) < <(TOTALBIT-bitn);//TOTALBIT是树的高度
}

然后根据这种关系，依次和对应的位置的数据交换就可以了，虽然交换后另一个位置的数据会改变，但是由于map是一对一的映射，所以不会再有位置映射到该位置，不会出错
[解决办法]
“一棵二叉排序树BST，按层次顺序排放在数组中，
就是和Heap结构一样，数组第i个元素的两个孩子在数组2*i+1和2*i+2位置上。”

可以知道该数组是分段有序的；
段的界限为1,3,7,15..............;
即 下标0-0，1-2,3-6,7-14的数据分别都是有序的；

另:对两分段有序的数组合并存在有时间复杂度O(n),空间复杂度为O(1)的算法（我没找到，有找到了的给个）；

如果：
1，0与1-2合并；
2，0-2与3-6合并；
3，0-6与7-14合并；
.......

则本算法的时间复杂度有递归式
f(1)=1;
f(n)=f(n/2)+n

由主定理可知该剃归式的复杂度为O(n);



[解决办法]
void midOrderSort(char *arrayInt, int size, int currentRoot, int &currentIndex)
{
if (currentRoot < size)
{
// 对当前根的左子树排序
midOrderSort(arrayInt, size, currentRoot*2+1, currentIndex);
if (currentRoot > = currentIndex && currentIndex + 1 < size)
{
int temp = arrayInt[currentIndex];
arrayInt[currentIndex] = arrayInt[currentRoot];
arrayInt[currentRoot] = temp;
currentIndex++;

// 若数组个数为奇数，则跳过中间结点，以防止对其计算两次
if (currentIndex == (size/2) && size % 2 != 0)
currentIndex++;
}
// 对当前根的右子树排序
midOrderSort(arrayInt, size, currentRoot*2+2, currentIndex);
}


int main(int argc, char* argv[])
{
char arrayint[7] = { '4 ', '2 ', '6 ', '1 ', '3 ', '5 ', '7 '};
int nIndex = 0;
int arraySize = sizeof(arrayint);

// //一棵满二叉树的最后一个节点肯定是最大的，不用对其进行排序
midOrderSort(arrayint, arraySize -1, 0, nIndex);
}