【专项刷题】— 归并

1、排序数组 - 力扣（LeetCode）

思路：

1. 先找一个中间值，然后递归左边部分和递归右半部分
2. 直到左边和右边只剩一个数了就返回，然后再合并左右两个部分
3. 
4. 代码：

   class Solution {
       int[] tmp;
       public int[] sortArray(int[] nums) {
           tmp =  new int[nums.length];
           mergeSort(nums, 0, nums.length-1);
           return nums;
       }
       public void mergeSort(int[] nums, int left, int right){
           if(left >= right){
               return;
           }
           // 1.根据中间值划分区间
           int mid = (right + left)/2;
           // 2.在左右两个区间里面排序
           mergeSort(nums, left, mid);
           mergeSort(nums, mid+1, right);
           // 3.合并两个有序数组
           int cur1 = left;
           int cur2 = mid+1;
           int i = 0;
           while(cur1 <= mid && cur2 <= right){
               tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
           }
           //处理没有遍历的数组
           while(cur1 <= mid){
               tmp[i++] = nums[cur1++];
           }
           while(cur2 <= right){
               tmp[i++] = nums[cur2++];
           }
           //覆盖原数组
           for(int j = left; j <= right; j++){
               nums[j] = tmp[j-left];
           }
       }
   }