Java实现归并排序出现栈溢出错误，求原因排查

你的代码触发栈溢出的核心原因是错误的子数组拆分逻辑导致无限递归，再加上递归终止条件设计不当，让递归无法正确收敛终止。下面具体拆解问题点，以及对应的修正方案：

问题1：子数组复制逻辑完全错误 #

你在拆分数组时用了增强for循环：

for (int i : a) { a[i] = seq[i]; }
for (int j : b) { b[j] = seq[s + j]; }

这里的i和j是数组中的元素值（新创建的数组初始值都是0），而不是索引！这意味着你一直在给a[0]重复赋值seq[0]，b[0]重复赋值seq[s]，完全没有把原数组的左右部分正确拆分到子数组中。最终导致拆分出的子数组和原数组内容完全不符，甚至会出现无限拆分同一个长度数组的情况，直接触发栈溢出。

问题2：递归终止条件设计不合理 #

带l和r参数的mergeSort方法里，你用if (seq.length < 2) { return seq; }作为终止条件，但这个方法的设计逻辑是基于原数组的索引范围来拆分，而非依赖传入数组的长度。更关键的是，当错误拆分出长度为0的子数组时，虽然这个条件会触发返回，但另一个子数组的长度和原数组完全一致，导致递归永远无法收敛，无限调用下去。

问题3：子数组长度计算错误 #

你计算子数组长度的逻辑有误：

int s = (l + r) / 2;
int[] a = new int[s];
int[] b = new int[seq.length - s];

当l=0、r=seq.length-1时，左子数组的范围是[l, s]，正确长度应该是s - l + 1，而非s；右子数组范围是[s+1, r]，长度是r - s。错误的长度计算会导致子数组要么越界，要么拆分不完整。

修正后的完整代码 #

public static int[] mergeSort(int[] seq) {
    // 提前处理空数组或单元素数组，避免不必要的递归
    if (seq == null || seq.length < 2) {
        return seq;
    }
    return mergeSort(seq, 0, seq.length - 1);
}

private static int[] mergeSort(int[] seq, int l, int r) {
    // 递归终止条件：当左右索引重合，说明只剩单个元素，直接返回该元素的数组
    if (l >= r) {
        return new int[]{seq[l]};
    }
    
    int mid = (l + r) / 2;
    // 递归拆分左右子数组
    int[] left = mergeSort(seq, l, mid);
    int[] right = mergeSort(seq, mid + 1, r);
    // 合并两个有序子数组
    return merge(left, right);
}

public static int[] merge(int[] ls, int[] rs) {
    int[] result = new int[ls.length + rs.length];
    int i = 0, l = 0, r = 0;
    
    // 同时遍历两个子数组，按顺序放入结果数组
    while (l < ls.length && r < rs.length) {
        if (ls[l] < rs[r]) {
            result[i++] = ls[l++];
        } else {
            result[i++] = rs[r++];
        }
    }
    
    // 处理左子数组剩余的元素
    while (l < ls.length) {
        result[i++] = ls[l++];
    }
    
    // 处理右子数组剩余的元素
    while (r < rs.length) {
        result[i++] = rs[r++];
    }
    
    return result;
}

修正说明 #

1. 修正递归终止条件：当l >= r时，直接返回包含当前单个元素的数组，确保递归能逐层收敛终止。
2. 正确拆分逻辑：通过索引范围[l, mid]和[mid+1, r]递归拆分，不需要手动复制子数组，让递归方法直接返回拆分后的有序子数组，避免复制错误。
3. 简化合并逻辑：合并方法的核心逻辑没问题，这里简化了剩余元素的处理，去掉了多余的条件判断，让代码更清晰。
4. 增加边界处理：在入口方法提前判断空数组或单元素数组的情况，避免不必要的递归调用。

这样修改后，递归会正确地将数组拆分到单个元素，再逐步合并，不会出现栈溢出问题。

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