基于第0索引排序二维数组的Java归并排序问题排查

你的代码存在三个关键错误，直接导致了元素被覆盖的异常：

• 子数组复制的索引逻辑错误
  在merge方法中，复制左半部分子数组时，你直接使用arr[i]，但当前处理的子数组起始位置是s，正确的索引应该是s + i；复制右半部分子数组时，右半部分的起始位置是mid + 1，而非n1，所以应该用arr[mid + 1 + i]来获取元素。

• 剩余元素处理的数组引用错误
  最后处理右半部分剩余元素的while循环中，错误地引用了left数组，应该改为right数组。

修正后的完整代码如下：

public static void mergeSort(long arr[][], int s, int e) {
    if (s < e) {
        int mid = s + (e - s) / 2;

        mergeSort(arr, s, mid);
        mergeSort(arr, mid + 1, e);

        merge(arr, s, mid, e);
    }
}

public static void merge(long arr[][], int s, int mid, int e) {
    int n1 = mid - s + 1, n2 = e - mid;
    long left[][] = new long[n1][2];
    long right[][] = new long[n2][2];
    
    // 修正左半部分复制逻辑
    for (int i = 0; i < n1; i++) {
        left[i] = arr[s + i];
    }

    // 修正右半部分复制逻辑
    for (int i = 0; i < n2; i++) {
        right[i] = arr[mid + 1 + i];
    }

    int i = 0, j = 0, k = s;

    while (i < n1 && j < n2) {
        if (left[i][0] < right[j][0])
            arr[k++] = left[i++];
        else
            arr[k++] = right[j++];
    }

    while (i < n1) {
        arr[k++] = left[i++];
    }

    // 修正右半部分剩余元素的引用
    while (j < n2) {
        arr[k++] = right[j++];
    }
}

public static void main(String[] args) {
    long arr[][] = { { 1, 4 }, { 3, 6 }, { 8, 4 }, { 7, 7 } };
    
    mergeSort(arr, 0, 3);
    
    for (int i = 0; i < 4; i++) {
        System.out.println(arr[i][0] + " " + arr[i][1]);
    }
}

运行修正后的代码，输出会是按第0索引排序后的结果：

1 4
3 6
7 7
8 4

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