这段C++归并排序代码为何出现段错误与运行时错误？

你的代码存在1个核心逻辑错误，直接触发写入临时数组时的缓冲区溢出，具体问题如下：

核心错误：中间索引mid计算错误 #

merge_sort函数中拆分区间的中间值计算逻辑完全错误：

// 错误写法
int mid = (end - beg) / 2;

这个计算得到的是区间长度的一半，是相对于区间起点的偏移量，不是原数组的绝对索引，只有当beg=0时计算结果碰巧正确，一旦递归到非0起点的子区间，拆分出的左右边界会完全错乱。

举个实际触发错误的场景：当递归处理子区间[2,3]（即beg=2、end=3）时，上述代码计算得到mid=0，后续递归调用右区间时会传入mid+1=1作为左边界，最终传入merge函数的参数变成beg=2、mid=0、end=3：

• 临时数组arr申请的长度是end - beg +1 = 2
• 合并循环中j从mid+1=1开始遍历，一直到end=3，总共需要写入的元素数量远大于arr的长度，直接触发数组越界写入，也就是你检测到的缓冲区溢出。

正确的mid计算应该是区间起点加上偏移量：

// 正确写法，同时避免了(beg+end)可能触发的整数溢出问题
int mid = beg + (end - beg) / 2;

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

void merge(int *str, int beg, int mid, int end) {
    int *arr = new int[end - beg + 1];
    int k = 0;
    int i = beg;
    int j = mid + 1;

    while (i <= mid && j <= end) {
        arr[k++] = str[i] < str[j] ? str[i++] : str[j++];
    }
    while (i <= mid) {
        arr[k++] = str[i++];
    }
    while (j <= end) {
        arr[k++] = str[j++];
    }
    for (i = beg; i <= end; i++) {
        str[i] = arr[i - beg];
    }
    delete[] arr;
}

void merge_sort(int *str, int beg, int end) {
    if (beg >= end)
        return;
    // 修正mid计算逻辑
    int mid = beg + (end - beg) / 2;
    merge_sort(str, beg, mid);
    merge_sort(str, mid + 1, end);
    merge(str, beg, mid, end);
}

可选优化建议 #

• 手动new/delete申请的临时数组容易出现内存泄漏，生产环境建议用std::vector<int>替代裸数组，自动完成内存回收
• 不要使用(beg + end)/2的方式计算mid，当beg和end数值较大时，二者相加可能超过int类型的最大值触发整数溢出，beg + (end - beg)/2是工业界通用的安全写法。

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