Java递归归并排序：手动数组切片与多数组合并策略

/**
 * 自定义数组切片方法，模拟 Arrays.copyOfRange 的功能。
 * 创建一个新数组，包含原数组从指定起始索引到结束索引（不包含）的元素。
 *
 * @param original 原始数组
 * @param from 起始索引（包含）
 * @param to 结束索引（不包含）
 * @return 包含指定范围元素的新数组
 * @throws IllegalArgumentException 如果 from 或 to 超出数组边界，或 from > to
 */
private static int[] copyArray(int[] original, int from, int to) {
    if (original == null) {
        throw new IllegalArgumentException("原始数组不能为null。");
    }
    if (from < 0 || from > original.length) {
        throw new IllegalArgumentException("起始索引超出数组范围。");
    }
    if (to < 0 || to > original.length) {
        throw new IllegalArgumentException("结束索引超出数组范围。");
    }
    if (from > to) {
        throw new IllegalArgumentException("起始索引不能大于结束索引。");
    }

    int[] result = new int[to - from];
    for (int i = from; i < to; i++) {
        result[i - from] = original[i];
    }
    return result;
}

public class MergeSort {

    // 主函数，用于测试归并排序
    public static void main(String[] args) throws IOException {
        // 示例输入，实际应用中可从控制台或文件读取
        int[] inputArray = {5, 2, 4, 6, 1, 3, 2, 6};
        System.out.println("原始数组: " + Arrays.toString(inputArray));

        mergeSort(inputArray);

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

        // 示例：合并三个数组
        int[] arr1 = {1, 3, 5, 7};
        int[] arr2 = {2, 4, 6, 8};
        int[] arr3 = {0, 9, 10};
        System.out.println("合并三个数组: " + Arrays.toString(arr1) + ", " + Arrays.toString(arr2) + ", " + Arrays.toString(arr3));
        int[] mergedThree = mergeArrays3(arr1, arr2, arr3);
        System.out.println("合并结果: " + Arrays.toString(mergedThree));
    }

    /**
     * 递归归并排序主方法。
     * 对给定的数组进行原地排序。
     *
     * @param A 待排序的整数数组
     */
    static void mergeSort(int[] A) {
        if (A.length > 1) {
            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); // 递归排序右半部分

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

    /**
     * 合并两个已排序的子数组到一个主数组中。
     *
     * @param targetArray 目标数组，用于存放合并后的结果
     * @param left 子数组L
     * @param right 子数组R
     */
    static void merge(int[] targetArray, int[] left, int[] right) {
        int i = 0; // 指向 targetArray 的当前位置
        int li = 0; // 指向 left 数组的当前位置
        int ri = 0; // 指向 right 数组的当前位置

        // 当左右两个子数组都有元素时，比较并选择较小的元素放入 targetArray
        while (li < left.length && ri < right.length) {
            if (left[li] <= right[ri]) { // 注意使用 <= 保证稳定性
                targetArray[i++] = left[li++];
            } else {
                targetArray[i++] = right[ri++];
            }
        }

        // 将 left 数组中剩余的元素复制到 targetArray
        while (li < left.length) {
            targetArray[i++] = left[li++];
        }

        // 将 right 数组中剩余的元素复制到 targetArray
        while (ri < right.length) {
            targetArray[i++] = right[ri++];
        }
    }

    // ... (copyArray 方法定义在此处或上方)
    private static int[] copyArray(int[] original, int from, int to) {
        // ... (同上方 copyArray 实现)
        if (original == null) {
            throw new IllegalArgumentException("原始数组不能为null。");
        }
        if (from < 0 || from > original.length) {
            throw new IllegalArgumentException("起始索引超出数组范围。");
        }
        if (to < 0 || to > original.length) {
            throw new IllegalArgumentException("结束索引超出数组范围。");
        }
        if (from > to) {
            throw new IllegalArgumentException("起始索引不能大于结束索引。");
        }

        int[] result = new int[to - from];
        for (int i = from; i < to; i++) {
            result[i - from] = original[i];
        }
        return result;
    }
}

    /**
     * 合并三个已排序的数组到一个新数组中。
     *
     * @param a 第一个已排序数组
     * @param b 第二个已排序数组
     * @param c 第三个已排序数组
     * @return 包含所有元素且已排序的新数组
     */
    public static int[] mergeArrays3(int[] a, int[] b, int[] c) {
        int[] result = new int[a.length + b.length + c.length];

        int i = 0, j = 0, l = 0, k = 0; // i, j, l 分别是 a, b, c 的指针；k 是 result 的指针

        // 当三个数组都有元素时，比较并选择最小的元素放入结果数组
        while (i < a.length && j < b.length && l < c.length) {
            if (a[i] <= b[j] && a[i] <= c[l]) {
                result[k++] = a[i++];
            } else if (b[j] <= a[i] && b[j] <= c[l]) {
                result[k++] = b[j++];
            } else { // c[l] 最小
                result[k++] = c[l++];
            }
        }

        // 处理剩余的两个数组（例如，a 和 b 还有元素，c 已遍历完）
        while (i < a.length && j < b.length) {
            if (a[i] <= b[j]) {
                result[k++] = a[i++];
            } else {
                result[k++] = b[j++];
            }
        }

        while (i < a.length && l < c.length) {
            if (a[i] <= c[l]) {
                result[k++] = a[i++];
            } else {
                result[k++] = c[l++];
            }
        }

        while (j < b.length && l < c.length) {
            if (b[j] <= c[l]) {
                result[k++] = b[j++];
            } else {
                result[k++] = c[l++];
            }
        }

        // 处理只剩下一个数组的情况
        while (i < a.length) {
            result[k++] = a[i++];
        }
        while (j < b.length) {
            result[k++] = b[j++];
        }
        while (l < c.length) {
            result[k++] = c[l++];
        }

        return result;
    }