和分治思想的第一次相遇
当问题的规模是可以划分的时候，分治的算法往往是很有效的：
不断分割问题的规模，直到子问题的规模足够小便直接求解，之后不断整合子问题的解得到更大规模的解，最后得到完全解。 归并排序就是分治算法的一个简单的例子。
可能有人觉得快速排序也是属于分治算法，但我不这么觉得，因为快速排序是先得到大问题的解的一部分，再靠子问题来完成解， 并没有整合子问题这一步，所以硬要说的话，快速排序应该是
“治分”算法。
简单图示（是不是有点太简单了）
如何分解？
归并排序把问题划为均匀的两个子问题，即左半区间和右半区间，于是得到递归函数：
#define MID(i) (i >> 1) /// i / 2
/*****************************************
函数：归并排序
说明：对区间[low, high)范围的数据排序
*****************************************/
void mergeSort(int* low, int* high)
{
int range = high - low; ///区间元素个数
if(range > 1) ///对于规模为1的子问题本身已经是解了，所以只处理规模大于1的子问题
{
int* mid = MID(range) + low; ///求出分割点
///递归求解子问题
mergeSort(low, mid);
mergeSort(mid, high);
merge(low, mid, high); ///再合并两个子问题，这个函数待会实现
}
}这里是不能应用尾递归优化的，因为节点信息需要保存，以便执行merge（合并）过程。 读者可以思考下对于规模为2的问题为什么不会出现无限递归。
怎么合并？
在合并两个子问题时我们知道子问题对应的区间已经是有序的。所以我们可以通过比较两区间当前的最小值，得到整个区间的最小值，不断选出最小值便可完成合并（类似选择排序） 整个过程的花费是线性的O（n），n为两区间元素个数和。 不过整个过程需要一个辅助数组来存放不断选出的最小值（总不能占别的元素的位置吧），所以为了效率，首先声明足够大的辅助数组：
#define MID(i) (i >> 1) /// i / 2
int* helper; ///辅助数组
/**********************************************
函数：归并函数
说明：合并有序区间[low, mid)和[mid, high)
left为左区间的遍历指针
right为右区间的遍历指针
helper为局部变量覆盖全局声明
这样做是为了减少代码行数
时间复杂度：O(high - low)
**********************************************/
void merge(int* low, int* mid, int* high, int* left, int* right, int* helper)
{
while(true)
{
if(*left <= *right) ///相等时下标小的优先，使得算法稳定
{
*(helper++) = *(left++);
if(left >= mid) ///左区间已经空了
{
while(right < high) *(helper++) = *(right++); ///把右区间剩下的复制过去
break; ///跳出循环（外层）
}
}
else
{
*(helper++) = *(right++);
if(right >= high) ///右区间空了
{
while(left < mid) *(helper++) = *(left++); ///把左区间剩下的复制过去
break; ///跳出外层循环
}
}
}
while(high > low) *(--high) = *(--helper); ///再复制回来
}
/*****************************************
函数：归并排序
说明：对区间[low, high)范围的数据排序
时间复杂度：O(nlgn)
*****************************************/
void mergeSortRoutine(int* low, int* high)
{
int range = high - low; ///区间元素个数
if(range > 1) ///对于规模为1的子问题本身已经是解了，所以只处理规模大于1的子问题
{
int* mid = MID(range) + low; ///求出分割点
///递归求解子问题
mergeSortRoutine(low, mid);
mergeSortRoutine(mid, high);
merge(low, mid, high, low, mid, helper); ///再合并两个子问题
}
}
/****************************************
函数：归并排序“外壳”
****************************************/
void mergeSort(int* low, int* high)
{
helper = new int[high - low]; ///辅助数组最多也就存输入的元素数
if(helper != nullptr)
{
mergeSortRoutine(low, high);
delete[] helper; ///释放内存
}
else return; ///空间不足，没法启动归并排序
}
时间复杂度
上面的归并排序的时间复杂度是很好分析的，最多有lgn层问题，每层均花费O(n)所以是O（nlgn），并且最坏和最好情况都是差不多的。
优化
关于归并排序的优化还是挺多的，这里先来讲一种很不错的优化： 在原始的归并函数中左右区间的元素都会按大小全部复制到辅助数组中去，之后再一一复制回来。这一过程没错不过却没有考虑那些原本就处于正确位置的元素。 比如当左区间空了的时候，此刻右区间剩下的元素还需要再复制到复制数组中吗？答案是不需要的，因为它们本来就已经在正确位置了：
/**********************************************
函数：优化版归并函数
说明：合并有序区间[low, mid)和[mid, high)
left为左区间的遍历指针
right为右区间的遍历指针
helper为局部变量覆盖全局声明
这样做是为了减少代码行数
时间复杂度：O(high - low)
**********************************************/
void merge(int* low, int* mid, int* high, int* left, int* right, int* helper)
{
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, mid)和[mid, high)
right为右区间的遍历指针
helper为局部变量覆盖全局声明
这样做是为了减少代码行数
时间复杂度：O(high - low)
**********************************************/
void mer