如何将数组三分实现三路归并排序？数组分割遇异常求助

你的代码核心问题出在数组分割的索引逻辑和大小计算细节上，直接导致了非法参数异常，以下是具体修正步骤：

核心错误点 #

1. 数组分割索引完全错误
   Arrays.copyOfRange(arr, start, end) 的规则是包含start、不包含end，你写的centre和right的起始索引大于结束索引（比如原数组长度9时，sizeLeft=3，centre的起始是3+1=4，结束是3），直接触发IllegalArgumentException。
2. 数组大小分配逻辑有误
   当余数mod为1时，你给left和centre都加了1，导致三个数组大小之和超过原数组长度；mod为2时的分配也不符合均匀分割的逻辑。
3. 测试循环逻辑错误
   用left.length作为循环条件遍历centre数组，一旦两个数组长度不一致，会触发数组越界异常。

修正后的完整代码 #

import java.util.Arrays;

public static int[] mergesort3(int[] arr) {
    int elements = arr.length;
    // 递归终止条件：数组长度<=1时无需排序，直接返回
    if (elements <= 1) {
        return arr;
    }

    int div = elements / 3;
    int mod = elements % 3;

    // 正确分配三个子数组的大小：余数依次分给前mod个数组，每个多1个元素
    int sizeLeft = div + (mod > 0 ? 1 : 0);
    int sizeCenter = div + (mod > 1 ? 1 : 0);
    // 用原数组长度减去前两个数组大小，避免计算错误
    int sizeRight = elements - sizeLeft - sizeCenter;

    // 正确计算分割索引范围
    int[] left = Arrays.copyOfRange(arr, 0, sizeLeft);
    int[] centre = Arrays.copyOfRange(arr, sizeLeft, sizeLeft + sizeCenter);
    int[] right = Arrays.copyOfRange(arr, sizeLeft + sizeCenter, elements);

    // 测试打印：分别遍历每个子数组
    System.out.println("Left子数组:");
    for (int num : left) System.out.print(num + " ");
    System.out.println("\nCentre子数组:");
    for (int num : centre) System.out.print(num + " ");
    System.out.println("\nRight子数组:");
    for (int num : right) System.out.print(num + " ");

    // 递归排序三个子数组后合并
    left = mergesort3(left);
    centre = mergesort3(centre);
    right = mergesort3(right);

    return merge3(left, centre, right);
}

额外提示 #

• merge3方法需要实现三路合并逻辑：同时遍历三个有序子数组，每次取出当前最小的元素放入结果数组，直到所有元素都被合并完成。
• 用elements - sizeLeft - sizeCenter计算sizeRight，能避免因余数分配错误导致的数组大小总和与原数组不匹配的问题。

内容的提问来源于stack exchange，提问作者Antonio Safi