思路

设定两个方法：用于递归的方法 mergeSort，返回类型为一个数组，参数：一个数组，本次需要处理的左下标 left 和右下标 right；用于合并两个数组，参数：数组a， 数组b

对于一个数组

• 若左下标与右下标之间有超过两个元素，意味着有继续划分的必要，以该规模的中位为分界，分为两个子区域，分别以各自区域为规模递归调用，并将这两个子区域返回的两个数组合并为一个数组，并将其返回
• 若规模不超过两个元素
  • 若只有一个元素，将其包围在数组中直接返回
  • 若有两个元素，按照大小排序放置在一个数组中进行返回

合并方法：将给定的两个数组按照大小排序进新的数组中，并将那个数组进行返回

代码

int[] mergeSort(int[] nums, int left, int right) {
        int[] leftNums, rightNums;
        if (left == right) {
            return new int[]{nums[left]};
        }

        // 至少还有三个元素
        if (right - left > 1) {
            int mid = (right + left) / 2;
            leftNums = mergeSort(nums, left, mid);
            rightNums = mergeSort(nums, mid + 1, right);

            return merge(leftNums, rightNums);
        } else {
            left = nums[left];
            right = nums[right];
            if (right > left) {
                return new int[]{left, right};
            } else {
                return new int[]{right, left};
            }
        }
    }

    int[] merge(int[] a, int[] b) {
        int[] merge = new int[a.length + b.length];
        int i = 0, j = 0, l = 0;

        while (i < a.length && j < b.length) {
            if (a[i] < b[j]) {
                merge[l] = a[i];
                ++i;
            } else {
                merge[l] = b[j];
                ++j;
            }
            ++l;
        }
        // 有一边没有全部合并
        if (i < a.length) {
            while (i < a.length) {
                merge[l] = a[i];
                i++;
                l++;
            }
        } else if (j < b.length) {
            while (j < b.length) {
                merge[l] = b[j];
                j++;
                l++;
            }
        }
        return merge;
    }