Java中递归实现归并排序与多路合并：无包依赖的数组操作实践

/**
 * 手动实现数组分片功能，类似于 Arrays.copyOfRange。
 * 创建一个新数组，包含 original 数组从 from 索引到 to 索引（不包含 to）的元素。
 *
 * @param original 原始数组
 * @param from 起始索引（包含）
 * @param to 结束索引（不包含）
 * @return 包含指定范围元素的新数组
 */
private static int[] copyArray(int[] original, int from, int to) {
    // 新数组的长度为 to - from
    int[] res = new int[to - from];
    // 遍历原始数组的指定范围，并复制到新数组中
    for (int i = from; i < to; i++) {
        res[i - from] = original[i];
    }
    return res;
}

/**
 * 递归实现归并排序。
 *
 * @param A 待排序的数组
 */
static void mergeSort(int[] A) {
    // 基本情况：如果数组长度小于等于1，则认为它已经有序，无需进一步排序
    if (A.length > 1) {
        int mid = A.length / 2; // 计算数组的中间索引

        // 使用手动实现的 copyArray 方法分割数组
        int[] leftArray = copyArray(A, 0, mid); // 左半部分：从0到mid-1
        int[] rightArray = copyArray(A, mid, A.length); // 右半部分：从mid到A.length-1

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

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

/**
 * 将两个已排序的子数组 l 和 r 合并到目标数组 a 中。
 *
 * @param a 目标数组，用于存放合并后的结果
 * @param l 左子数组（已排序）
 * @param r 右子数组（已排序）
 */
static void merge(int[] a, int[] l, int[] r) {
    int i = 0, li = 0, ri = 0; // i: 目标数组指针, li: 左子数组指针, ri: 右子数组指针

    // 当左右子数组都有元素时，比较它们当前指向的元素，将较小的放入目标数组
    while (li < l.length && ri < r.length) {
        if (l[li] < r[ri]) {
            a[i++] = l[li++]; // 左子数组元素较小，放入目标数组，并移动相应指针
        } else {
            a[i++] = r[ri++]; // 右子数组元素较小（或相等），放入目标数组，并移动相应指针
        }
    }

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

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

/**
 * 将三个已排序的数组 a, b, c 合并成一个大的有序数组。
 *
 * @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, k = 0, resPtr = 0; // i, j, k 分别为数组 a, b, c 的指针；resPtr 为结果数组指针

    // 循环直到所有数组的元素都被处理完毕
    while (i < a.length || j < b.length || k < 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 = (k < c.length) ? c[k] : Integer.MAX_VALUE;

        // 找到三个值中的最小值，并将其添加到结果数组中
        if (valA <= valB && valA <= valC) {
            // 确保 valA 确实来自有效索引，避免在所有数组都耗尽时重复添加 MAX_VALUE
            if (i < a.length) {
                result[resPtr++] = a[i++];
            } else {
                // 如果 valA 是 MAX_VALUE 且被选为最小，说明所有数组都已耗尽，可以提前退出
                break;
            }
        } else if (valB <= valA && valB <= valC) {
            if (j < b.length) {
                result[resPtr++] = b[j++];
            } else {
                break;
            }
        } else { // valC 是最小值
            if (k < c.length) {
                result[resPtr++] = c[k++];
            } else {
                break;
            }
        }
    }
    return result;
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
// import java.util.Arrays; // 根据要求，不使用 Arrays 包

public class MergeSortWithManualCopy {

    public static void main(String[] args) throws IOException {
        BufferedReader R = new BufferedReader(new InputStreamReader(System.in));
        System.out.print("请输入数组大小: ");