47.归并排序
题目链接：
题目描述：
题目示例：
解法 (归并排序)：
算法思路：
归并排序的流程充分体现了「分而治之」的思想，大体过程分为两步：
分：将数组一分为二为两部分，一直分解到数组的长度为 1，使整个数组的排序过程被分为「左半部分排序」+「右半部分排序」;
治：将两个较短的「有序数组合并成一个长的有序数组」，一直合并到最初的长度。
C++ 算法代码：
class Solution {
public:
//归并排序的算法
vector<int> tmp; //用于存放两个有序数组合并后的结果
void mergesort(vector<int>& nums, int left, int right) {
if(left == right) {
return;
}
//1、选择中间点划分区间
int mid = (right - left) / 2 + left;
//将数组分成两块：[left, mid] [mid + 1, right]
//2、把左右区间排序
mergesort(nums, left, mid);
mergesort(nums, mid + , right);
cur1 = left, cur2 = mid + , i = ;
(cur1 <= mid && cur2 <= right) {
tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
}
(cur1 <= mid) {
tmp[i++] = nums[cur1++];
}
(cur2 <= right) {
tmp[i++] = nums[cur2++];
}
( i = left; i <= right; i++) {
nums[i] = tmp[i - left];
}
}
{
tmp.(nums.());
(nums, , nums.() - );
nums;
}
};
