为何我的归并排序程序输出异常（0 4 0 0 0 0 0 0）？

我写了一段归并排序程序，直接传入测试数值后，运行输出结果多为0，想排查是while循环错误还是递归逻辑的问题？以下是我的代码和输出结果：

void merge(int arr[], int s, int e)
{

    int mid = s + (e - s) / 2;

    // 要拆分的两个子数组长度
    int m = mid - s + 1;
    int n = e - mid;

    int* arr1 = new int[m];
    int* arr2 = new int[n];

    // 将主数组的值复制到arr1和arr2
    int x = s;
    for (int i = 0; i < m; i++) {
        arr1[i] = arr[x + i];
    }
    for (int j = mid + 1; j < n; j++) {
        arr2[j] = arr[mid + 1 + j];
    }

    int i = 0; // arr1的索引
    int j = 0; // arr2的索引
    int k = s; // 主数组的起始索引

    while (i < m && j < n) {
        if (arr1[i] <= arr2[j]) {
            arr[k] = arr1[i];
            i++;
            k++;
        }

        else {
            arr[k] = arr2[j];
            k++;
            j++;
        }

        while (i < m) {
            arr[k] = arr1[i];
            k++;
            i++;
        }

        while (j < n) {
            arr[k] = arr2[j];
            k++;
            j++;
        }
    }

    delete[] arr1;
    delete[] arr2;
}

// 递归拆分函数
void divide(int arr[], int s, int e)
{

    if (s >= e)
        return;
    int mid = s + (e - s) / 2;
    divide(arr, s, mid);
    divide(arr, mid + 1, e);
    merge(arr, s, e);
}

#include <iostream>
using namespace std;

int main()
{

    int n = 8;
    int arr[8] = { 4, 8, 9, 7, 6, 2, 3, 1 };

    divide(arr, 0, n - 1);

    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }

    return 0;
}

输出结果：0 4 0 0 0 0 0 0

问题根源分析 #

递归逻辑divide函数是正确的，问题全部出在merge函数里：

1. arr2的复制循环错误
   原代码中复制arr2的循环逻辑完全错误：

   • 循环起始索引错误：arr2是新创建的数组，索引应从0开始，而非mid+1；
   • 循环条件不成立：以首次merge为例，mid=3、n=4，j从4开始时j < n不成立，循环直接跳过，导致arr2所有元素都是未初始化的垃圾值（大概率为0）。
   • 正确写法：

     for (int j = 0; j < n; j++) {
         arr2[j] = arr[mid + 1 + j];
     }
     

2. 剩余元素处理的循环嵌套错误
   原代码将处理arr1、arr2剩余元素的两个while循环，放到了外层while (i < m && j < n)的内部，导致外层循环仅执行一次就会强制处理完其中一个数组的剩余元素，排序逻辑彻底混乱。

   • 正确做法是将这两个while移到外层循环之外，等两个数组的共同元素比较完成后，再处理剩余元素：

     while (i < m && j < n) {
         if (arr1[i] <= arr2[j]) {
             arr[k] = arr1[i];
             i++;
             k++;
         } else {
             arr[k] = arr2[j];
             k++;
             j++;
         }
     }
     // 处理arr1剩余元素
     while (i < m) {
         arr[k] = arr1[i];
         k++;
         i++;
     }
     // 处理arr2剩余元素
     while (j < n) {
         arr[k] = arr2[j];
         k++;
         j++;
     }
     

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