解法：经典的归并排序
思路：
1.先求中间点
mid = left + (right - left) / 2;
2.思想
先把数组分为两块，再进行左区间的递归分割（先一直分割左区间），分割到只剩一个元素后就可以返回，此时就再去右边递归分割。两边都分割完返回后，在上层，把两区间（或者说两个有序数组合并成一个数组），一直向上合并，直到返回到第一层，就完成了归并排序。
3.辅助数组
在把两个有序数组合并的时候，需要一个辅助数组，作用是：用它来存储两个有序数组合并后的结果，之后再赋给nums，才算结束一次合并。递归中开辟新数组消耗太大，所以推荐定义一个全局的数组，时间效率上，会有显著提升。
4.和快排的区别
仔细想想归并和快排的思想是相似的，但可以分析出，归并其实像是二叉树的后序遍历，快排像是二叉树的前序遍历。
细节：
合并两个有序数组时，因为循环条件，可能其中一个数组的指针没遍历到最后，所以while结束，需要额外两个while再次处理没有遍历完的情况。
附上完整代码：
class Solution {
public:vector<int> tmp;vector<int> sortArray(vector<int>& nums) {tmp.resize(nums.size());mergeSort(nums,0,nums.size()-1);return nums;}void mergeSort(vector<int>& nums,int l,int r){if(l >= r)return;//1.划分中间结点int mid = l + (r - l) / 2;//2.递归两个区间，类似于二叉树的后序遍历mergeSort(nums,l,mid);mergeSort(nums,mid+1,r);//3.合并两个有序数组int cur1 = l,cur2 = mid+1,i = 0;while(cur1 <= mid && cur2 <= r)tmp[i++] = nums[cur1] < nums[cur2] ? nums[cur1++] : nums[cur2++]; //其中一个数组没走完，接着赋值给tmpwhile(cur1 <= mid) tmp[i++] = nums[cur1++];while(cur2 <= r) tmp[i++] = nums[cur2++];//4.还原，辅助的tmp，赋给numsfor(int i = l;i<=r;i++)nums[i] = tmp[i - l];}
};
)
