C++二维数组归并排序传入超4个元素出现segmentation fault如何解决

问题核心原因 #

你的段错误是归并排序递归计算中点的逻辑错误导致无限递归栈溢出，具体错误点：

• mergesort函数第三个参数实际是当前排序区间的右边界（你命名为size极易混淆），你计算中点的代码int m = p + int((size - 1) / 2);只在左边界p=0时成立，当递归到左边界不为0的子区间时，中点计算完全错误，会出现子区间永远无法缩小到递归终止条件p < size不成立的情况，无限递归导致栈溢出触发段错误。
  比如你测试5个元素的场景，初始调用是mergesort(arr1, 0, 4)，第一次递归右半区间是mergesort(arr1, 3, 4)，按你的公式计算m = 3 + (4-1)/2 = 4，接下来会继续调用mergesort(arr1, 3,4)，永远不会终止。

修复方案 #

1. 修正中点计算逻辑 #

把mergesort函数里的中点计算改为：

int m = p + (size - p) / 2;

更建议同步修改参数命名避免语义混淆：

// 第三个参数修改为右边界r，语义更清晰
void mergesort(int **Arr, int l, int r)
{
    if (l < r)
    {
        int m = l + (r - l) / 2; // 正确的中点计算，同时避免大数溢出
        mergesort(Arr, l, m);
        mergesort(Arr, m + 1, r);
        merge(Arr, l, m, r);
    }
}

2. 适配高速要求的性能优化 #

你当前merge函数里每次为每个子元素calloc新空间、复制值再free的操作会严重拖慢速度，既然你存储的是指针，直接复制指针即可，不需要额外申请子元素空间：

void merge(int **Arr, int p, int m, int r)
{
    int n1 = m - p + 1;
    int n2 = r - m;

    int **L = (int **)malloc(n1 * sizeof(int *));
    int **M = (int **)malloc(n2 * sizeof(int *));

    // 直接复制指针，无需额外开空间存int值
    for (int i = 0; i < n1; i++) L[i] = Arr[p + i];
    for (int j = 0; j < n2; j++) M[j] = Arr[m + 1 + j];

    int i = 0, j = 0, k = p;
    while (i < n1 && j < n2)
    {
        if (L[i][0] <= M[j][0]) Arr[k++] = L[i++];
        else Arr[k++] = M[j++];
    }
    while (i < n1) Arr[k++] = L[i++];
    while (j < n2) Arr[k++] = M[j++];

    // 仅需释放指针数组，无需释放每个子元素
    free(L);
    free(M);
}

修改后性能会提升数倍，也减少了内存分配出错的概率。

可选C++原生优化方案 #

如果你是在C++环境下使用，直接调用标准库的稳定排序实现更简单、性能也经过工业级优化：

#include <algorithm>
// 一行完成排序，按子数组首元素升序排列
std::stable_sort(arr1, arr1 + a, [](int* a, int* b) { return a[0] < b[0]; });

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