在排序算法的发展历史上，归并排序具有特殊的地位，它是第一个可以在最坏的情况下依然可以保持O(nlogn)运行时间的确定性排序算法。
与起泡排序通过反复调用单趟扫描交换类似，归并排序也可以理解为是通过反复调用所谓的二路归并算法实现的。所谓二路归并，就是将两个有序序列合并成一个有序序列。归并排序所需的时间业主要决定于各趟二路归并所需的时间总和。
二路归并属于迭代算法。每步迭代中，只需要比较两个待归并向量的首元素，将小者去除并追加到输出向量的末尾，该元素在原向量中的后继向量则成为新的首元素。如此往复，直到某一向量为空。最后，将另一个非空的向量整体接至输出向量末尾。
图片发自简书App
图片发自简书App
//
// Created by krislyy on 2018/11/14.
//
#ifndef ALGORITHM_MERGESORT_H
#define ALGORITHM_MERGESORT_H
namespace Algorithm {
template <typename T>
static void Merge(T *array, int lo, int mi, int hi) {
//设置临时变量来存储新的有序数列
T temp[hi - lo + 1];
int pos = 0, lpos = lo, hpos = mi + 1;
while (lpos <= mi && hpos <= hi) { //比较两组有序序列
if (array[lpos] < array[hpos]) {
temp[pos++] = array[lpos++];
} else {
temp[pos++] = array[hpos++];
}
} //比较两个数组中较小的元素放入新数组中
while (lpos <= mi) { temp[pos++] = array[lpos++]; }
while (hpos <= hi) { temp[pos++] = array[hpos++]; }
//将临时数组放入原数组中
for (int i = 0; i < pos; ++i) {
array[i+lo] = temp[i]; //放入原数组lo~hi区间，此时这个区间有序
}
}
template <typename T>
static void MergeSort(T *array, int lo, int hi) {
int mi = (hi + lo) / 2; //以中点为边界
if (lo < hi) {
MergeSort(array, lo, mi);
MergeSort(array, mi+1, hi); //分别排序
Merge(array, lo, mi, hi); //归并
}
}
}
#endif //ALGORITHM_MERGESORT_H
