ge(int* low, int* mid, int* high, int* right, int* helper)
{
///收缩左边界，不再考虑左区间原本位于正确位置的元素
while(*low <= *right)
if(++low >= mid) return; ///如果左区间的元素全部在正确位置，那么右区间也是如此，直接返回
int* left = low; ///设置左区间遍历指针
*(helper++) = *(right++); ///别浪费上面循环失败的比较结果。。。
if(right >= high) ///右区间空了
while(left < mid) *(helper++) = *(left++); ///把左区间剩下的复制过去
else while(true)
{
if(*left <= *right) ///相等时下标小的优先，使得算法稳定
{
*(helper++) = *(left++);
if(left >= mid) break; ///左区间扫描完直接跳出外层循环，此时右区间剩下来的元素本来就处于正确位置
}
else
{
*(helper++) = *(right++);
if(right >= high) ///右区间空了
{
while(left < mid) *(helper++) = *(left++); ///把左区间剩下的复制过去
break; ///跳出外层循环
}
}
}
while(right > low) *(--right) = *(--helper); ///再复制回来，不过要跳过右区间剩下的元素
} 虽然在最坏情况下和原始的归并函数一样，但是大部分情况还是有优化的，特别是当数组原本有序时，每层只需简单遍历O(n/2)个元素，比快速排序更高效。
减少的“倒腾”次数的期望
即下面cnt的平均值：
int cnt = 0; ///计数器
void merge(int* low, int* mid, int* high, int* right, int* helper)
{
while(*low <= *right)
{
cnt++; ///左边多一个元素不用参与复制
if(++low >= mid)
{
cnt += high - right; ///右边都不用参加
return;
}
}
int* left = low;
*(helper++) = *(right++);
if(right >= high)
while(left < mid) *(helper++) = *(left++);
else while(true)
{
if(*left <= *right)
{
*(helper++) = *(left++);
if(left >= mid)
{
cnt += high - right; ///右边不用参加复制的元素个数
break;
}
}
else
{
*(helper++) = *(right++);
if(right >= high)
{
while(left < mid) *(helper++) = *(left++);
break;
}
}
}
while(right > low) *(--right) = *(--helper); ///再复制回来，不过要跳过右区间剩下的元素
} 当左右区间元素个数均为 k/2时，左区间不用参与复制的元素个数为 i 的条件为前 i 小的元素都被分在了左边，并且第 i + 1大元素被分在了右边，但第k/2大元素要单独考虑。 右边不用参与复制的元素个数和左区间是一样的，因为是对称的。于是得到下面的级数：
下面是我的测试数据（元素互异且随机排列）：
可以看出这项优化平均减少O（n）次多余的操作。
使叶子“变粗”
同样归并排序也可以用插入排序来优化，同样也是因为对于小规模的数据插入排序常数小的缘故。并且由于引进插入排序我们知道叶子宽度一定大于1，因此可以简化归并函数：
#define FACTOR 10 ///叶子宽度
#define MID(i) (i >> 1) /// i / 2
int* helper; ///辅助数组
/**********************************************
函数：优化版归并函数
说明：合并有序区间[low, mid)和[mid, high)
right为右区间的遍历指针
helper为局部变量覆盖全局声明
这样做是为了减少代码行数
时间复杂度：O(high - low)
**********************************************/
void merge(int* low, int* mid, int* high, int* right, int* helper)
{
///收缩左边界，不再考虑左区间原本位于正确位置的元素
while(*low <= *right)
{
if(++low >= mid)
return; ///如果左区间的元素全部在正确位置，那么右区间也是如此，直接返回
}
int* left = low; ///设置左区间遍历指针
*(helper++) = *(right++); ///别浪费上面循环失败的比较结果。。。
///因为叶子大于1，所以之前那两句就不用了。
while(true)
{
if(*left <= *right) ///相等时下标小的优先，使得算法稳定
{
*(helper++) = *(left++);
if(left >= mid) break; ///左区间扫描完直接跳出外层循环，此时右区间剩下来的元素本来就处于正确位置
}
else
{
*(helper++) = *(right++);
if(right >= high) ///右区间空了
{
while(left < mid) *(helper++) = *(left++); ///把左区间剩下的复制过去
break; ///跳出外层循环
}
}
}
while(right > low) *(--right) = *(--helper); ///再复制回来，不过要跳过右区间剩下的元素
}
/*************************************
函数：优化版插入排序
说明：对区间[low, high)的数据排序
时间复杂度：O(n + inverse)
*************************************/
static void improvedInsertionSort(int* low , int* high)
{
for(int* cur = low; ++cur < high; ) ///实际是从第二个元素开始插入，因为第一个已经有序了
{
int tmp = *cur; ///临时保存要插入的值
int* destPos = cur; ///记录当前要插入的元素的正确安放位置，这里初始化为本来的位置
///把第一次测试单独提出来
if(*(--destPos) > tmp)
{
do
{
*(destPos + 1) = *destPos;
}while(--destPos >= low && *destPos > tmp); ///测试上一个是否是目标位置
*(destPos + 1) = tmp; ///最后一次测试失败使得destIndex比实际小1
}
}
}
/*****************************************
函数：归并排序
说明：对区间[low, high)范围的数据排序
时间复杂度：O(nlgn)
*****************************************/
void mergeSortRoutine(int* low, int* high)
{
int range = high - low; ///区间元素个数
if(range > FACTOR) ///对于规模为1的子问题本身已经是解了，所以只处理规模大于1的子问题
{
int* mid = MID(range) + low; ///求出分割点
///递归求解子问题
mergeSortRoutine(low, mid);
mergeSortRoutine(mid, high);
merge(low, mid, high, mid, helper); ///再合并两个子问题
}
else improvedInsertionSort(low, high);
}
/****************************************
函数：归并排序“外壳”
****************************************/
void mergeSort(int* low, int* high)
{
helper = new int[high - low]; ///辅助数组最多也就存输入的元素数
if(helper != nullptr)
{
mergeSortRoutine(low, high);
delete[] helper; ///释放内存
}
else return; ///空间不足，没法启动归并排序
}
自底向上的归并排序
上面递归版的归并排序的分解步骤是通过划分父问题才得到子问题，但其实子问题是可以被我们直接找到的，因为一个子问题的标识是一个区间，而区间是由左右端点的数字确定的。 所以我们可以直接计算出我们目前想得到的子问题的区