#define MID(i) (i >> 1) /// i / 2
#define NEXT_GAP(i) (i <<= 1)    ///下一个步长

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++);   ///别浪费上面循环失败的比较结果。。。
    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);   ///再复制回来，不过要跳过右区间剩下的元素
}

/************************************************
    函数：自底向上版归并排序
    说明：对区间[low, low + range)范围的数据排序
    时间复杂度：O(nlgn)
************************************************/
void mergeSortRoutine(int* low, int* high, int range)
{
    for(int gap = 2; MID(gap) < range; NEXT_GAP(gap))
        for(int* right = low + gap, * mid = low + MID(gap); mid < high; right += gap, mid += gap)
            merge(right - gap, mid, right > high ? high : right, mid, helper);
}

/****************************************
    函数：归并排序“外壳”
****************************************/
void mergeSort(int* low, int* high)
{
    helper = new int[high - low];   ///辅助数组最多也就存输入的元素数
    if(helper != nullptr)
    {
        mergeSortRoutine(low, high, high - low);
        delete[] helper;    ///释放内存
    }
    else return;    ///空间不足，没法启动归并排序
}

后记