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

/**
 * 手动复制数组指定范围的元素。
 *
 * @param original 原始数组。
 * @param from     起始索引（包含）。
 * @param to       结束索引（不包含）。
 * @return 包含原始数组指定范围元素的新数组。
 * @throws IllegalArgumentException 如果from或to参数无效。
 */
private static int[] copyArray(int[] original, int from, int to) {
    // 参数校验：确保起始索引和结束索引的有效性
    if (from < 0 || to > original.length || from > to) {
        throw new IllegalArgumentException(
            String.format("无效的数组复制范围：from=%d, to=%d, original.length=%d", from, to, original.length));
    }

    int[] result = new int[to - from]; // 新数组的长度为 to - from
    for (int i = from; i < to; i++) {
        result[i - from] = original[i]; // 将原始数组的元素复制到新数组的相应位置
    }
    return result;
}

/**
 * 对给定数组进行递归归并排序。
 *
 * @param A 待排序的数组。
 */
static void mergeSort(int[] A) {
    // 递归终止条件：如果数组长度小于或等于1，则认为它已经有序
    if (A.length > 1) {
        int mid = A.length / 2; // 计算数组中点

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

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

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

/**
 * 将两个已排序的子数组合并到一个目标数组中。
 *
 * @param targetArray 目标数组，合并后的结果将存储在此数组中。
 * @param leftArray   第一个已排序的子数组。
 * @param rightArray  第二个已排序的子数组。
 */
static void merge(int[] targetArray, int[] leftArray, int[] rightArray) {
    int i = 0; // targetArray 的当前索引
    int leftPtr = 0; // leftArray 的当前索引
    int rightPtr = 0; // rightArray 的当前索引

    // 当两个子数组都还有元素时，比较它们的首元素并将较小的元素放入 targetArray
    while (leftPtr < leftArray.length && rightPtr < rightArray.length) {
        if (leftArray[leftPtr] < rightArray[rightPtr]) {
            targetArray[i++] = leftArray[leftPtr++];
        } else {
            targetArray[i++] = rightArray[rightPtr++];
        }
    }

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

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

/**
 * 将三个已排序的数组合并成一个已排序的新数组。
 *
 * @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 是结果数组的指针

    // 只要任一数组还有未合并的元素，就继续循环
    while (i < a.length || j < b.length || l < c.length) {
        // 获取当前指针指向的元素值，如果数组已耗尽，则使用 Integer.MAX_VALUE 作为哨兵值
        int valA = (i < a.length) ? a[i] : Integer.MAX_VALUE;
        int valB = (j < b.length) ? b[j] : Integer.MAX_VALUE;
        int valC = (l < c.length) ? c[l] : Integer.MAX_VALUE;

        // 找到三个值中的最小值，并将其放入结果数组
        if (valA <=