Java实现归并排序：自定义数组切片与多路归并策略

/**
 * 自定义数组切片方法，模拟Arrays.copyOfRange的功能。
 * 复制原始数组中从from（包含）到to（不包含）的元素。
 *
 * @param original 原始数组
 * @param from 起始索引（包含）
 * @param to 结束索引（不包含）
 * @return 包含指定范围元素的新数组
 */
private static int[] copyArray(int[] original, int from, int to) {
    // 新数组的长度为 to - from
    int[] result = new int[to - from];
    // 遍历原始数组的指定范围，并将元素复制到新数组中
    for (int i = from; i < to; i++) {
        result[i - from] = original[i]; // 确保新数组从索引0开始填充
    }
    return result;
}

public class MergeSort {

    // 主方法，用于测试归并排序
    public static void main(String[] args) {
        // 示例输入
        int[] inputArray = {38, 27, 43, 3, 9, 82, 10};
        System.out.println("原始数组: " + java.util.Arrays.toString(inputArray));

        mergeSort(inputArray);

        System.out.println("排序后数组: " + java.util.Arrays.toString(inputArray));

        // 示例三路归并
        int[] arr1 = {1, 5, 9};
        int[] arr2 = {2, 6, 10};
        int[] arr3 = {3, 7, 11};
        int[] merged3 = mergeArrays3(arr1, arr2, arr3);
        System.out.println("三路归并结果: " + java.util.Arrays.toString(merged3));
    }

    /**
     * 递归归并排序主函数。
     * 对给定的整数数组进行原地排序。
     *
     * @param A 待排序的整数数组
     */
    public static void mergeSort(int[] A) {
        // 基本情况：如果数组长度小于2，则认为它已经有序，直接返回
        if (A.length < 2) {
            return;
        }

        // 计算数组的中间索引
        int mid = A.length / 2;

        // 使用自定义的copyArray方法创建左右子数组
        // leftArray 包含从索引 0 到 mid-1 的元素
        int[] leftArray = copyArray(A, 0, mid);
        // rightArray 包含从索引 mid 到 A.length-1 的元素
        int[] rightArray = copyArray(A, mid, A.length);

        // 递归地对左右子数组进行排序
        mergeSort(leftArray);
        mergeSort(rightArray);

        // 将已排序的左右子数组合并回原数组A
        merge(A, leftArray, rightArray);
    }

    /**
     * 自定义数组切片方法，模拟Arrays.copyOfRange的功能。
     * 复制原始数组中从from（包含）到to（不包含）的元素。
     *
     * @param original 原始数组
     * @param from 起始索引（包含）
     * @param to 结束索引（不包含）
     * @return 包含指定范围元素的新数组
     */
    private static int[] copyArray(int[] original, int from, int to) {
        int[] result = new int[to - from];
        for (int i = from; i < to; i++) {
            result[i - from] = original[i];
        }
        return result;
    }
}

public class MergeSort {
    // ... (previous methods: main, mergeSort, copyArray) ...

    /**
     * 二路归并函数，将两个已排序的子数组l和r合并到主数组a中。
     *
     * @param a 目标数组，合并后的结果将存储在此数组中
     * @param l 左子数组（已排序）
     * @param r 右子数组（已排序）
     */
    public static void merge(int[] a, int[] l, int[] r) {
        int i = 0, li = 0, ri = 0; // i用于a的索引，li用于l的索引，ri用于r的索引

        // 当左右子数组都还有元素时，比较它们的首元素并将其较小者放入a中
        while (li < l.length && ri < r.length) {
            if (l[li] <= r[ri]) { // 使用 <= 确保排序的稳定性
                a[i++] = l[li++];
            } else {
                a[i++] = r[ri++];
            }
        }

        // 如果左子数组还有剩余元素，将其全部复制到a中
        while (li < l.length) {
            a[i++] = l[li++];
        }

        // 如果右子数组还有剩余元素，将其全部复制到a中
        while (ri < r.length) {
            a[i++] = r[ri++];
        }
    }
}

public class MergeSort {
    // ... (previous methods: main, mergeSort, copyArray, merge) ...

    /**
     * 三路归并函数，将三个已排序的数组arr1, arr2, arr3合并成一个大的有序数组。
     *
     * @param arr1 第一个已排序的数组
     * @param arr2 第二个已排序的数组
     * @param arr3 第三个已排序的数组
     * @return 合并后的有序数组
     */
    public static int[] mergeArrays3(int[] arr1, int[] arr2, int[] arr3) {
        // 创建一个足够大的结果数组来容纳所有元素
        int[] result = new int[arr1.length + arr2.length + arr3.length];
        // 初始化三个数组的指针和结果数组的指针
        int p1 = 0, p2 = 0, p3 = 0, k = 0;

        // 循环直到所有数组的元素都被处理完毕
        while (p1 < arr1.length || p2 < arr2.length || p3 < arr3.length) {
            // 获取当前指针指向的元素值，如果数组已耗尽，则使用Integer.MAX_VALUE作为