归并排序的思路为将区间划分为两块，将两部分都排好序后再合并在一起。思路图如下：
这个就是整个的递归过程，合并的过程没有详细描述，可以看代码mer()
//归并排序 [L，R]区间上进行归并排序 归并排序用到了递归
//时间复杂度是O(N*logN),空间复杂度是O(N)，保持稳定性
template<typename T>
void mer(vector<T>&vec, int L, int mid, int R) {
int i = 0;
int p1 = L;
int p2 = mid+1;
vector<T>temp(R-L+1);
while (p1 <= mid && p2 <= R) {
temp[i++] = (vec[p1] < vec[p2]) ? vec[p1++] : vec[p2++];
}
while (p1 <= mid) {
temp[i++] = vec[p1++];
}
while (p2 <= R) {
temp[i++] = vec[p2++];
}
for (int i = 0; i < R - L + 1; i++) {
vec[L + i] = temp[i];
}
}
template<typename T>
void merge_sort(vector<T>&vec, int L, int R) {
if (L == R)return;
int mid = L + ((R - L) >> 1);
merge_sort(vec, L, mid); //将左半部排好序
merge_sort(vec, mid + 1, R);//将右半部排好序
mer(vec, L, mid, R);
}
