思路：分治思想，通过不断地合并两个有序的数组达到最终的排序结果。需要O(n)的辅助空间，即空间换时间。相较于快速排序的优点在于其稳定。
void merge(vector<int>& nums, int l, int mid, int r) {
vector<int> tmp(r-l+1); //开辟辅助空间
int i = l, j = mid+1, k = 0;
while(i <= mid && j <= r) {
if(nums[i] <= nums[j]) { //此处只有是<=才会是稳定的，若是<则不稳定。
tmp[k++] = nums[i++];
}
else tmp[k++] = nums[j++];
}
while(i <= mid) {
tmp[k++] = nums[i++];
}
while(j <= r) {
tmp[k++] = nums[j++];
}
for(i = 0; i < tmp.size(); ++i) {
nums[l+i] = tmp[i];
}
}
void mergeSort(vector<int>& nums, int l, int r) {
if(l >= r) return;
int mid = (l + r) / 2;
mergeSort(nums, l, mid);
mergeSort(nums. mid+1, r);
merge(nums, l, mid, r);
}
