归并的思想是：将两个已经有序的序列合并成一个有序的序列，这也是归并排序的核心算法。
合并low-mid以及mid+1-high两个序列，需要开辟一个等长的临时序列，所以空间复杂度是所有排序算法中最高的n
类别
排序方法
最好时间
最坏时间
平均时间
空间复杂度
稳定性
序列特征
适用于
归并排序
/
nlogn
nlogn
nlogn
n
稳定
短有序序列+短有序序列+短…
分治
n个元素二路归并，要归并log2n趟
每趟归并时间复杂度o(n),最坏情况下，每合并两个序列要比较（m+n-1）次
所以总的时间复杂度是o(nlog2n)
归并排序 VS 希尔排序
希尔排序：初始分组时每组元素个数：2，这两个元素距离：d， 小分组自己组内直接插入排序。
归并排序：初始分组时每组元素个数：2，这两个元素距离：相邻，两个小分组一起排序后合成一个大分组
归并排序 VS 快速排序
都是递归排序，为什么归并排序时间复杂度是n，快速排序是logn
归并排序：每一轮都会开辟分组大小的辅助空间，最后一次递归的辅助数组大小为n，递归栈消耗的空间为logn, 但是n>logn,所以时间复杂度就是n。
快速排序：不开辟这么大的辅助空间，所以时间复杂度是仅仅是递归栈的大小，logn
这部分是个人见解，可能有错误！
编程注意事项：
1.走第一步拷贝的原因是，正在原序列上更改，所以形式参数用引用
2.一个子表归并结束，而另一个子表还有元素未遍历时，直接将后序元素搬入结果序列末尾
vector<int> b(20); void merge(vector<int> &a,int low, int mid, int high) { //合并low~mid;mid+1~high b.assign(a.begin(), a.end());//复制元素到b中 int i,k,j;//k是新序列的指针，i是二路归并左边的指针，j是右边的指针 for(i=low,j=mid+1,k=i; i<=mid&&j<=high; k++) { if (b[i] < b[j]) a[k] = b[i++];//更小的存入新序列 else a[k] = b[j++]; } while (i <= mid) a[k++] = b[i++]; while (j<=high) a[k++] = b[j++]; } void mergeSort(vector<int> &a, int low, int high) { if (low < high) { int mid = (low + high) / 2; mergeSort(a,low, mid);//左半部分归并排序 mergeSort(a,mid + 1, high);//右半部分排序 merge(a,low,mid,high);//归并 } } void Sort() { int n; cout << "请输入元素个数："; cin >> n; vector<int> num(n+1); for (int i = 1; i < n + 1; i++)cin >> num[i]; cout << " 归并排序："; mergeSort(num,1,num.size() - 1); for (int i = 1; i < num.size(); i++)cout << num[i] << " "; } int main() { Sort(); }