归并排序

思路：分治思想，通过不断地合并两个有序的数组达到最终的排序结果。需要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);
}