归并排序

归并排序，经典的排序算法，基于分而治之的思想。

核心思想

要将一个数组排序，可以先（递归地）将它分成两半，分别对这两半排序，然后再将结果归并起来。

时间复杂度

时间复杂度为O(nlogn)。

空间复杂度

空间复杂度为O(n)，因为需要一个额外O*(*n)空间的辅助数组来帮助归并过程。

稳定性

稳定。

代码示例

public int[] sortArray(int[] nums) {
    mergeSort(nums, 0, nums.length - 1);
    return nums;
}

/**
 * 归并排序
 *
 * @author chengzhy
 * @param nums 需要排序的数组
 * @param left 左边界
 * @param right 右边界
 * @date 2022/2/19 13:00
 */
private void mergeSort(int[] nums, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        /**
         * 分治思想：同时对左半区间和右半区间排序
         * 排序完后再合并
         */
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        // 利用辅助数组合并
        merge(nums, left, mid, right);
    }
}

/**
 * 合并区间
 *
 * @author chengzhy
 * @param nums 需要排序的数组
 * @param left 左边界
 * @param mid 中间点
 * @param right 右边界
 * @date 2022/2/19 13:00
 */
private void merge(int[] nums, int left, int mid, int right) {
    int[] temp = new int[right - left + 1];
    int i = left, j = mid + 1, k = 0;
    // 将小的先添加进去
    while (i <= mid && j <= right) {
        temp[k++] = (nums[i] < nums[j]) ? nums[i++] : nums[j++];
    }
    // 左半区剩余
    while (i <= mid) {
        temp[k++] = nums[i++];
    }
    // 右半区剩余
    while (j <= right) {
        temp[k++] = nums[j++];
    }
    // 更新原数组
    for (i = 0; i < temp.length; i++) {
        nums[i + left] = temp[i];
    }
}