归并排序算法时间复杂度较为稳定，一般为nlogn,而快速排序受源数组排序影响较大，今天来学习归并排序。
一.归并排序代码
首先上代码：可以直接运行
#include<bits/stdc++.h>
using namespace std;
void insertsort(vector<int>&nums, int left,int mid, int right)
{
if (nums[mid] <= nums[mid + 1])
return;
for (int i = left+1; i <= right; ++i)
{
int idx = i;
while (idx > left && nums[idx] < nums[idx - 1])
{
swap(nums[idx], nums[idx-1]);
--idx;
}
}
}
vector<int>temp;
void merge(vector<int>&nums,int left,int mid,int right)
{
if (nums[mid] <= nums[mid + 1])
return;
for (int i = left; i <= right; ++i)
temp[i] = nums[i];
int x = left, y = mid + 1;
for (int i = left; i <= right; ++i)
{
if (y > right|| (y<=right&&x<=mid&&temp[x] <= temp[y]))
{
nums[i] = temp[x];
++x;
}
else if (x>mid||(x<=mid&&temp[x]>temp[y]))//条件可省略
{
nums[i] = temp[y];
++y;
}
}
}
void mergesort(vector<int>&nums,int left,int right)
{
if (left >=right) return;
int mid = left + (right - left)/2;
mergesort(nums, left, mid);
mergesort(nums, mid + 1, right);
if (mid - left + 1 <= 10)
insertsort(nums, left, mid, right);
else
merge(nums, left, mid, right);
}
int main()
{
vector<int>nums = { 2,1,4,6,5,88,99,0,999};
int n = nums.size();
temp.resize(n);
mergesort(nums,0,n-1);
for (auto &num : nums)
cout << num << endl;
return 0;
}二.代码详解
1.主函数
主函数较为简单，就是定义数组，然后调用mergesort函数，最后打印输出。
值得注意的是在主函数中我们将一个temp数组定义了大小，这个数组是辅助数组，在详细的有序合并的操作中用得到，因为我们需要好多次的合并，每次合并后的数组都不一样。
2.mergesort函数
这个函数就是一个递归函数，不断地去分割，直到分割到最后只有一个元素时，它会退出分割操作，然后这个元素会和分割出的另一半元素进行合并操作，合并完成跳到上一级继续合并。
3.merge合并函数
在合并函数中，首先如果左右两个已经是有序的，则不需要合并，直接返回。
然后我们将要合并的left到right之间的元素拷贝到temp辅助数组中，
因为原来左右两边就是有序的，所以我们只关注左右两边的起始索引，将较小的那个放进nums[i]中，
特别要注意的是元素过界问题，因为只是归并操作，索引并不会突破数组上限，从而造成结果不正确而很难发现出问题。
如果说y右侧索引超出了限定right，我们将temp[x]赋值给nums[i],此时x不会出上限。
或者说y没出索引，x也没出索引，那么当temp[x]<temp[y]时，我们也将temp[x]赋值给nums[i].
其余情况均是temp[y]赋值给nums[i]。
4.插入排序insertsort
当right-left特别小的时候，我们可以直接使用插入排序，想象一下我们只有两个元素[2,1],
插入排序只需要swap两个值即可，而不需要赋值给赋值数组。
插入排序的思想是前面的数组元素是有序的，那么我遍历到第idx个元素时,我要把它插入到前面的合适位置，特别地如果这个值比较大，那么它不用动，
如果它比较小，那么让他和idx-1的数进行不断交换，直到遇到合适的位置。
