思路：分治思想狰腌，通過不斷地合并兩個有序的數組達到最終的排序結果除破。需要O(n)的輔助空間，即空間換時間琼腔。相較于快速排序的優(yōu)點在于其穩(wě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]) { //此處只有是<=才會是穩(wěn)定的，若是<則不穩(wěn)定丹莲。
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);
}
