C++实现归并排序无报错输出异常，求定位merge函数错误

你的代码一共存在2处明显错误，修改后即可正常运行： #

错误1：merge函数剩余元素处理笔误 #

你在处理第二个子数组剩余元素的循环中，错误递增了i变量，代码如下：

while (j < n2) {
    arr[p] = arr2[j];
    i++; // 此处为错误代码
    p++;
}

因为循环的终止条件是j < n2，你一直递增i不会改变j的值，会导致程序进入死循环，甚至越界访问内存输出乱码。
修复方案：将i++替换为j++即可。 #

错误2：merge_sort函数mid下标计算错误 #

你当前计算中间下标的逻辑是错误的：

int mid = start + (end - 1) / 2;

这个计算方式没有考虑start的偏移量，会导致左右区间拆分错误，排序逻辑完全失效。
修复方案：将mid计算逻辑替换为int mid = start + (end - start) / 2; #

修复后可正常运行的完整代码 #

#include <iostream>
using namespace std;

void merge(int arr[], int start, int mid, int end) {
    int n1 = mid - start + 1;
    int n2 = end - mid;
    
    int arr1[n1], arr2[n2];
    for (int i = 0; i < n1; i++) {
        arr1[i] = arr[start + i];
    }
    for (int j = 0; j < n2; j++) {
        arr2[j] = arr[mid + 1 + j];
    }

    int i = 0, j = 0, p = start;
    
    while (i < n1 && j < n2) {
        if (arr1[i] <= arr2[j]) {
            arr[p] = arr1[i];
            i++;
        } else {
            arr[p] = arr2[j];
            j++;
        }
        p++;
    }
    while (i < n1) {
        arr[p] = arr1[i];
        i++;
        p++;
    }

    while (j < n2) {
        arr[p] = arr2[j];
        j++;
        p++;
    }
}

void merge_sort(int arr[], int start, int end) {
    if (start >= end) {
      return;
    }
    int mid = start + (end - start) / 2;
    merge_sort(arr, start, mid);
    merge_sort(arr, mid + 1, end);
    merge(arr, start, mid, end);
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = { 6, 5, 12, 10, 9, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
    
    merge_sort(arr, 0, n - 1);
    cout << "The sorted array is: " << endl;
    printArray(arr, n);
    return 0;
}

运行后输出：

The sorted array is: 
1 5 6 9 10 12 

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