排序----归并排序

数据结构与算法

先是进行分组，真正的排序是在后面的归并部分。归并的时候还要额外空间。
这里要把两部分全部比较，不用把中间剩出来。
因此：

group(nums, left, mid-1);//这是错的
group(nums, mid + 1, right);

public class Solution {
    public static void group(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = (left + right) / 2;
        group(nums, left, mid);
        group(nums, mid + 1, right);
        mergeSort(nums, left, mid, right);
    }
    public static void mergeSort(int[] nums, int left, int mid, int right) {
        int[] a = new int[nums.length];
        int i = left;
        int j = mid + 1;
        for (int k = left; k <= right; k++) {
            a[k] = nums[k];
        }
        for (int k = left; k <= right; k++) {
            if (i > mid) {// i本身是小于medium，但是现在已经比medium大了，说明右半部分已经消耗完了，插入左半部分
                nums[k] = a[j++];
            } else if (j > right) {// 同理,j本身应该是小于right的，但是现在已经比right大了，说明左半部分已经消耗完了，插入右半部分
                nums[k] = a[i++];
            } else if (a[i] > a[j]) {// 如果右半部分的当前值比左半部分的当前值大，则插入左半部分当前值
                nums[k] = a[j++];
            } else {
                nums[k] = a[i++];// 如果右半部分比左半部分小或者等，则插入右半部分
            }
        }
    }
    public static void main(String[] args) {
        int[] nums = {1, 2, 55, 6, 3, 2, 4, 5, 6, 8, 9, 0};
        group(nums, 0, nums.length - 1);
        System.out.println(Arrays.toString(nums));
    }
}