自定义仅支持ArrayList与Comparator的归并排序移tmp至外层后3元素测试失败原因

你遇到的问题核心在于对ArrayList构造参数的误解，以及递归复用临时数组时的操作逻辑冲突，咱们结合3元素的测试场景一步步拆解：

1. 最直接的触发原因：ArrayList初始化错误 #

你在外层mergeSort方法里创建临时数组的代码是：

new ArrayList<T> (high + 1)

这里要注意：ArrayList的这个构造参数是初始容量，不是实际元素个数！也就是说，这个tmp对象的size()还是0，只是底层数组预留了high+1个元素的空间。

当你的merge方法里尝试用tmp.set(k, element)去设置元素时（比如处理3元素数组时，k从0开始），会直接抛出IndexOutOfBoundsException——因为tmp里根本没有第0个元素（size为0，索引范围是不存在的）。这就是3元素测试用例直接崩掉的最直观原因。

2. 隐藏的复用冲突问题（即使解决了初始化） #

假设你修复了初始化问题（比如用new ArrayList<>(Collections.nCopies(high+1, null))让tmp的size等于容量），还可能遇到递归阶段的复用冲突：
比如3元素数组[a,b,c]，递归流程是：

• 拆分[0,2]为[0,1]和[2,2]
• 先处理[0,1]，拆分为[0,0]和[1,1]，合并后会修改tmp的0-1位置
• 再处理[2,2]，无操作
• 最后合并[0,1]和[2,2]，需要用到tmp的0-2位置

如果你的merge逻辑没有严格限定操作的区间，比如没有从当前merge的low位置开始写入tmp，就可能导致之前的合并结果被意外覆盖，最终排序结果错误。

解决方案 #

针对这两个问题，给你两种可行的修复思路：

方案一：正确初始化临时数组的size #

把外层创建tmp的代码改成：

ArrayList<T> tmp = new ArrayList<>(Collections.nCopies(high + 1, null));

这样tmp的size直接等于high+1，每个位置初始为null，merge方法里的set操作就不会再抛出索引越界异常。同时要确保merge逻辑中只操作当前合并区间对应的tmp索引（从low到high），避免干扰其他递归阶段的数据。

方案二：调整merge逻辑，适配复用的临时数组 #

更稳妥的方式是修改merge方法，每次合并前清空tmp，然后通过add元素填充，最后复制回原数组的对应区间：

private static <T> void merge(ArrayList<T> array, Comparator<T> c, int low, int mid, int high, ArrayList<T> tmp) {
    tmp.clear(); // 清空之前的内容
    int i = low, j = mid + 1;
    
    // 合并两个子数组到tmp
    while (i <= mid && j <= high) {
        if (c.compare(array.get(i), array.get(j)) <= 0) {
            tmp.add(array.get(i));
            i++;
        } else {
            tmp.add(array.get(j));
            j++;
        }
    }
    // 复制剩余元素
    while (i <= mid) tmp.add(array.get(i++));
    while (j <= high) tmp.add(array.get(j++));
    
    // 将tmp的内容写回原数组的对应区间
    for (int k = 0; k < tmp.size(); k++) {
        array.set(low + k, tmp.get(k));
    }
}

这种方式不需要关心tmp的初始size，每次合并都从0开始填充tmp，再精准写回原数组的low到high位置，既避免了索引越界，也不会有复用冲突。

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