核心思想:先递归划分，然后合并的时候相当于合并两个有序数组，需要用到一个额外数组，最后把额外数组的元素依次赋给原数组，注意函数参数为引用
//统一接口void Merge_sort(vector<int> &num, int n){vector<int> temp(n);Msort(num, temp, 0, n-1);}//递归划分void Msort(vector<int> &num, vector<int> temp, int l, int rightend){int center;if(l < rightend){center = l + (rightend - l) / 2;Msort(num, temp, l, center);Msort(num, temp, center+1, rightend);Merge(num, temp, l, center+1, rightend);}}//合并,相当于两个有序数组并列在一排第一个数组从l开始，到r-1结束，第二个数组从r开始，到rightend结束void Merge(vector<int> &num, vector<int> temp, int l, int r, int rightend){int leftend = r - 1;int index = l;//存放数组Temp初始位置int n = rightend - l + 1;//数组长度while(l <= leftend && r <= rightend){if(num[l] <= num[r]) temp[index++] = num[l++];else temp[index++] = num[r++];}while(l <= leftend)temp[index++] = num[l++];while(r <= rightend)temp[index++] = num[r++];for(int i = 0; i < n; ++i, --rightend)num[rightend] = temp[rightend];}