2、实现归并排序

算法步骤

归并排序算法是一个递归过程，边界条件为当输入序列仅有一个元素时，直接返回，具体过程如下：

如果输入内只有一个元素，则直接返回，否则将长度为 $n$ 的输入序列分成两个长度为 $n / 2$ 的子序列；
分别对这两个子序列进行归并排序，使子序列变为有序状态；
设定两个指针，分别指向两个已经排序子序列的起始位置；
比较两个指针所指向的元素，选择相对小的元素放入到合并空间（用于存放排序结果），并移动指针到下一位置；
重复步骤 3 ~ 4 直到某一指针达到序列尾；
将另一序列剩下的所有元素直接复制到合并序列尾。

图解算法

代码实现

/**
 * 归并排序
 *
 * @param arr
 * @return arr
 */
public static int[] mergeSort(int[] arr) {
    if (arr.length <= 1) {
        return arr;
    }
    int middle = arr.length / 2;
    int[] arr_1 = Arrays.copyOfRange(arr, 0, middle);
    int[] arr_2 = Arrays.copyOfRange(arr, middle, arr.length);
    return merge(mergeSort(arr_1), mergeSort(arr_2));
}

/**
 * Merge two sorted arrays
 *
 * @param arr_1
 * @param arr_2
 * @return sorted_arr
 */
public static int[] merge(int[] arr_1, int[] arr_2) {
    int[] sorted_arr = new int[arr_1.length + arr_2.length];
    int idx = 0, idx_1 = 0, idx_2 = 0;
    while (idx_1 < arr_1.length && idx_2 < arr_2.length) {
        if (arr_1[idx_1] < arr_2[idx_2]) {
            sorted_arr[idx] = arr_1[idx_1];
            idx_1 += 1;
        } else {
            sorted_arr[idx] = arr_2[idx_2];
            idx_2 += 1;
        }
        idx += 1;
    }
    if (idx_1 < arr_1.length) {
        while (idx_1 < arr_1.length) {
            sorted_arr[idx] = arr_1[idx_1];
            idx_1 += 1;
            idx += 1;
        }
    } else {
        while (idx_2 < arr_2.length) {
            sorted_arr[idx] = arr_2[idx_2];
            idx_2 += 1;
            idx += 1;
        }
    }
    return sorted_arr;
}

上面的Arrays.copyOfRange 确实这段代码的一个性能瓶颈。每次递归调用都创建新数组，会带来大量的内存分配和数据拷贝开销。但是实际上我们只需要告诉排序方法：“请对 arr 数组中从 left 索引到 right 索引的这部分进行排序”。这样，所有的操作都在同一个原始数组上进行，完全避免了创建中间数组。

为了实现这一点，我们需要引入一个辅助数组（通常称为 temp），用于在合并（merge）阶段暂存数据。这个 temp 数组只需在整个排序过程开始时创建一次，然后反复复用。

下面是优化后的代码实现：

public class OptimizedMergeSort {

    /**
     * 归并排序的主入口
     * @param arr 待排序的数组
     */
    public static int[] mergeSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        // 创建一个与原数组等长的辅助数组，用于合并操作
        int[] temp = new int[arr.length];
        // 调用递归排序方法，传入索引范围
        sort(arr, 0, arr.length - 1, temp);
        return temp;
    }

    /**
     * 递归地对数组 arr 的 [left, right] 区间进行排序
     * @param arr 原始数组
     * @param left 排序区间的左边界（包含）
     * @param right 排序区间的右边界（包含）
     * @param temp 辅助数组
     */
    private static void sort(int[] arr, int left, int right, int[] temp) {
        if (left >= right) {
            return; // 只有一个元素或区间无效时，递归结束
        }

        int mid = left + (right - left) / 2;
        // 递归排序左半部分
        sort(arr, left, mid, temp);
        // 递归排序右半部分
        sort(arr, mid + 1, right, temp);

        // 【性能优化点】如果左半部分的最大值已经小于等于右半部分的最小值，
        // 说明整个区间已经有序，无需再进行合并操作。
        if (arr[mid] <= arr[mid + 1]) {
            return;
        }

        // 合并两个已排序的区间
        merge(arr, left, mid, right, temp);
    }

    /**
     * 合并两个已排序的区间: arr[left...mid] 和 arr[mid+1...right]
     * @param arr 原始数组
     * @param left 左区间起始索引
     * @param mid 左区间结束索引
     * @param right 右区间结束索引
     * @param temp 辅助数组
     */
    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
	    // 拷贝当前区间的数据到辅助数组
         for (int i = left; i <= right; i++) {
         	temp[i] = arr[i];
         }

        int i = left;      // 指向 temp 中左半部分的起始位置
        int j = mid + 1;   // 指向 temp 中右半部分的起始位置
        int k = left;      // 指向原数组 arr 中待填充的位置

        // 比较 temp 中的左右两部分，将较小的元素放回原数组 arr
        while (i <= mid && j <= right) {
            if (temp[i] <= temp[j]) {
                arr[k++] = temp[i++];
            } else {
                arr[k++] = temp[j++];
            }
        }

        // 处理剩余元素
        // 如果左半部分还有剩余，将其全部复制回 arr
        while (i <= mid) {
            arr[k++] = temp[i++];
        }

        while (j <= right) {
            arr[k++] = temp[j++];
        }
        
    }
}

算法分析

稳定性：稳定
时间复杂度：最佳： $O (n l o g n)$ ，最差： $O (n l o g n)$ ，平均： $O (n l o g n)$
空间复杂度： $O (n)$