【归并排序】排序数组（medium）

题⽬链接：912. 排序数组

题⽬描述：

给你⼀个整数数组 nums，请你将该数组升序排列。
⽰例 1：
输⼊：nums = [5,2,3,1]
输出：[1,2,3,5]
⽰例 2：
输⼊：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]

解法（归并排序）：

算法思路：

归并排序的流程充分的体现了「分⽽治之」的思想，⼤体过程分为两步：
◦ 分：将数组⼀分为⼆为两部分，⼀直分解到数组的⻓度为 1 ，使整个数组的排序过程被分为「左半部分排序」 + 「右半部分排序」；
◦ 治：将两个较短的「有序数组合并成⼀个⻓的有序数组」，⼀直合并到最初的⻓度。

算法代码：

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 = (left + right) / 2;// [left, mid] [mid + 1, right]// 2. 先把左右区间排个序mergeSort(nums, left, mid);mergeSort(nums, mid + 1, right);// 3. 合并两个有序数组int cur1 = left, cur2 = mid + 1, 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++];// 4. 还原for(int j = left; j <= right; j++) nums[j] = tmp[j - left];}
}