自定义归并排序处理二维int数组时无限运行问题排查求助

问题原因 #

• 核心问题1：缺少递归终止条件，导致无限递归
  归并排序的拆分逻辑必须设置终止边界，当前代码未判断输入数组的长度，当数组长度≤1时本身已经有序，不需要继续拆分排序，直接返回即可。缺失该判断会导致程序持续对长度为1甚至0的数组做拆分操作，永远无法进入合并逻辑，表现为无限执行甚至栈溢出。
• 核心问题2：比较逻辑与降序要求不符
  当前merge方法中的判断条件left[i][1] < right[j][1]实现的是按数组第二个元素升序排列，和你需要的降序逻辑相反。

修正后的完整代码 #

void mergeSort(int[][] boxTypes){
    // 新增递归终止条件
    if (boxTypes.length <= 1) {
        return;
    }
    int mid = boxTypes.length / 2;
    int[][] left = new int[mid][2];
    int[][] right = new int[boxTypes.length - mid][2];
    
    for(int i = 0; i < mid; i++) left[i] = boxTypes[i];
    for(int i = mid; i < boxTypes.length; i++) right[i - mid] = boxTypes[i];
    
    mergeSort(left);
    mergeSort(right);
    
    merge(left, right, boxTypes);
}

void merge(int[][] left, int[][] right, int[][] boxTypes){
    int i = 0; int j = 0; int k = 0;
    
    while(i < left.length && j < right.length){
        // 修改比较逻辑为降序：左数组元素更大时优先取左数组
        if(left[i][1] > right[j][1]){
            boxTypes[k][0] = left[i][0];
            boxTypes[k][1] = left[i++][1];
        } else {
            boxTypes[k][0] = right[j][0];
            boxTypes[k][1] = right[j++][1];
        }
        k++;
    }
    
    // 剩余元素改为逐属性赋值，保持逻辑统一避免潜在问题
    while(i < left.length) {
        boxTypes[k][0] = left[i][0];
        boxTypes[k][1] = left[i++][1];
        k++;
    }
    while(j < right.length) {
        boxTypes[k][0] = right[j][0];
        boxTypes[k][1] = right[j++][1];
        k++;
    }
}

用测试用例[[5,10],[2,5],[4,7],[3,9]]运行上述代码，可得到预期输出[[5,10],[3,9],[4,7],[2,5]]。

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