递归实现MergeSort输出异常，求排查代码问题

用递归实现归并排序后，代码运行结果异常：输出数组前三个元素有序，接着出现若干0，之后部分元素有序、部分无序。原代码如下：

import java.util.*;
import java.io.*; 

public class Main {
    public static void merge(int[]arr, int low, int mid, int high) {
        int temp[] = new int[high + 1];
        int index = 0;
        int left = low;
        int right = mid + 1;
        while (left <= mid && right <= high) {
            if (arr[left] <= arr[right]) {
                temp[index] = arr[left];
                left++;
            } else {
                temp[index] = arr[right];
                right++;
            }
            index++;
        }
        //for exhaustion of any of the parts
        while (left <= mid ){
            temp[index] = arr[left];
            left++;
            index++;
        }
        while (right <= high ){
            temp[index] = arr[right];
            right++;
            index++;
        }
        //copying elements to array
        for (int i = 0; i < temp.length; i++) {
            arr[i] = temp[i];
        }
        //printing arr
        for (int i = 0; i < temp.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    public static void mergesort(int[]arr, int low, int high) {
        //base case
        if (low >= high) {
            return;
        }
        int mid = (low + high) / 2;
        mergesort(arr, low, mid);
        mergesort(arr, mid + 1, high);
        merge(arr, low, mid, high);
    }
    
    public static void main(String[] args) {
        int[] arr = { 2, 3, 46, 5, 8, 7, 6 };
        int n = arr.length;
        mergesort(arr, 0, n - 1);
    }
}

错误分析 #

• 临时数组长度错误：int temp[] = new int[high + 1]; 创建了长度为high+1的数组，但当前合并的是[low, high]区间，实际需要的长度是high - low + 1。多余的数组位置默认值为0，后续复制时会把这些0写入原数组，导致输出出现0。
• 数组复制索引错误：复制temp到原数组时，arr[i] = temp[i]是从数组开头覆盖，但当前合并的是[low, high]区间，应该把temp中的元素写入原数组的[low, high]位置，即arr[low + i] = temp[i]。
• 打印范围错误：打印时遍历了整个temp数组，会输出未使用的0，应该只打印当前合并完成的[low, high]区间元素。

修正后的代码 #

import java.util.*;
import java.io.*; 

public class Main {
    public static void merge(int[]arr, int low, int mid, int high) {
        // 修正：临时数组长度为当前合并区间的元素个数
        int temp[] = new int[high - low + 1];
        int index = 0;
        int left = low;
        int right = mid + 1;
        while (left <= mid && right <= high) {
            if (arr[left] <= arr[right]) {
                temp[index] = arr[left];
                left++;
            } else {
                temp[index] = arr[right];
                right++;
            }
            index++;
        }
        // 处理剩余元素
        while (left <= mid ){
            temp[index] = arr[left];
            left++;
            index++;
        }
        while (right <= high ){
            temp[index] = arr[right];
            right++;
            index++;
        }
        // 修正：将temp元素复制到原数组的[low, high]区间
        for (int i = 0; i < temp.length; i++) {
            arr[low + i] = temp[i];
        }
        // 修正：只打印当前合并完成的区间
        for (int i = low; i <= high; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println(); // 换行方便查看每一步合并结果
    }

    public static void mergesort(int[]arr, int low, int high) {
        if (low >= high) {
            return;
        }
        int mid = (low + high) / 2;
        mergesort(arr, low, mid);
        mergesort(arr, mid + 1, high);
        merge(arr, low, mid, high);
    }
    
    public static void main(String[] args) {
        int[] arr = { 2, 3, 46, 5, 8, 7, 6 };
        int n = arr.length;
        mergesort(arr, 0, n - 1);
    }
}

修正后运行代码，会正确输出每一步合并的有序区间，最终整个数组完全有序，不会出现0和无序的情况。

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