Java归并排序递归实现出现StackOverflowError问题求助

嘿，我来帮你搞定这个问题！你遇到的Exception in thread "main" java.lang.StackOverflowError是因为递归没有终止条件，加上merge方法里还有索引错误，咱们一步步修复：

1. 递归终止条件缺失（核心问题） #

你的msort方法没有设置递归终止的边界——当数组长度为1（或空）时，根本不需要再拆分排序，直接返回原数组就行。现在的代码会无限递归拆分，直到栈内存被耗尽，触发栈溢出错误。

修改后的msort代码（新增终止条件）：

public static int[] msort(int a[]) {
    // 新增：数组长度<=1时直接返回，终止递归
    if (a.length <= 1) {
        return a;
    }
    
    int n = a.length;
    int m = n / 2;
    int l[] = new int[m];
    int r[];
    if(n % 2 == 0) {
        r = new int[m];
    } else {
        r = new int[m+1];
    }
    for(int i = 0; i < m; i++) {
        l[i] = a[i];
    }
    for(int j = 0; j < r.length; j++) {
        r[j] = a[m+j];
    }
    int res[] = new int[n];
    l = msort(l);
    r = msort(r);
    res = merge(l, r);
    return res;
}

2. merge方法的索引错误 #

你的merge方法里有两处明显的索引逻辑错误，会导致结果数组赋值混乱甚至索引越界：

• 左边数组剩余元素时，错误使用rp++作为结果数组的索引，应该用跟踪结果数组的resp++
• 右边数组剩余元素时，同样错误使用rp++作为结果数组索引，并且赋值语句里的索引逻辑混乱

修改后的merge代码：

public static int[] merge(int l[], int r[]) {
    int len = l.length + r.length;
    int res[] = new int[len];
    int lp = 0, rp = 0, resp = 0;
    while(lp < l.length || rp < r.length) {
        if(lp < l.length && rp < r.length) {
            if(l[lp] < r[rp]) {
                res[resp++] = l[lp++];
            } else {
                res[resp++] = r[rp++];
            }
        } else if(lp < l.length) {
            // 修复：用resp++跟踪结果数组位置
            res[resp++] = l[lp++];
        } else if(rp < r.length) {
            // 修复：用resp++跟踪结果数组位置，正确取r[rp]后rp自增
            res[resp++] = r[rp++];
        }
    }
    return res;
}

把这两处修改完成后，你的归并排序应该就能正常运行啦！

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