自底向上归并排序合并数组时触发Abort trap 6错误排查

问题现象 #

• 手动实现的自底向上归并排序处理小规模数组时运行正常，数组规模增大后稳定触发Abort trap报错
• 调试定位到程序执行delete[] aux;语句时收到SIGABRT信号
• 编译环境：Visual Studio Code搭载Apple clang version 11.0.3编译器
• 替换手动new申请的动态数组为std::vector后问题消失，需要定位代码的根本错误

问题复现代码 #

void botup_mergesort(int *arr, int begin, int end)
{
    for (int merge_sz = 1; merge_sz < (end - begin); merge_sz *= 2)
    {
        for (int par = begin; par < end; par += merge_sz*2)
        {
            const int &sub_begin = par;
            const int &sub_end = std::min(par + merge_sz*2, end);

            if (sub_end - sub_begin <= 1)
            {
                continue;
            }

            const int& m = par + merge_sz;

            const int &merge_size = sub_end - sub_begin;
            int *aux = new int[merge_size];
            int cnt = -1;

            int p1 = sub_begin;
            int p2 = m;
            while (p2 < end && p1 < m && p2 < sub_end)
            {
                if (arr[p1] <= arr[p2])
                    aux[++cnt] = arr[p1++];
                else if (arr[p1] > arr[p2])
                    aux[++cnt] = arr[p2++];
            }

            while (p1 < m)
            {
                aux[++cnt] = arr[p1++];
            }

            while (p2 < sub_end && p2 < end)
            {
                aux[++cnt] = arr[p2++];
            }

            for (int i = sub_begin, m_cnt = 0; i < sub_end; ++i)
            {
                arr[i] = aux[m_cnt++];
            }
            delete[] aux;
        }
    }
}

void sort(int *arr, int begin, int end) { botup_mergesort(arr, begin, end); }

int main()
{
    int arr[] = {2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 5, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 5};
    // int arr2[] = {2, 2, 2, 2, 2, 8, 5, 3, 9, 4, 6, 2, 1, 5, 1, 5, 7};
    int n = sizeof(arr) / sizeof(int);
    cout << "Size: " << n << endl;

    sort(arr, 0, n);

    print(arr, n);
    return 0;
}

根本错误原因 #

报错核心原因是堆内存溢出破坏了堆结构，触发点在最后一个不完整分段的合并逻辑：

1. 分段中点没有做边界截断：代码中计算左右分段分界点m时直接写const int& m = par + merge_sz;，没有和数组尾端end取最小值做截断。当处理数组末尾长度不足merge_sz的残段时，m会超出数组实际长度。
   以测试用例中长度为41的数组为例，当merge_sz=16时，最后一个分段起点par=32，计算得到的m=32+16=48，已经超出数组最大下标40。
2. 左段拷贝逻辑无边界保护：拷贝左段剩余元素的循环仅判断p1 < m，没有限制p1不能超过分段右端点sub_end和数组总长度end。当m值越界时，p1会持续向后访问数组外的非法内存，同时向仅申请了merge_size长度的aux数组写入远超其容量的元素，直接破坏堆内存的校验结构。
   内存分配器在执行delete[]时会校验堆块的头信息，发现结构被破坏就会直接触发SIGABRT终止程序，这就是报错定位在delete[] aux行的原因。
3. 小规模数组不触发问题的原因：小数组长度下merge_sz增长到最后一轮时，不会出现par + merge_sz大幅超过end的残段场景，不会触发越界写，因此可以正常运行。

另外代码中存在不规范写法：用const左值引用绑定算术运算生成的临时int值，虽然语法上const引用会延长临时变量生命周期不会直接报错，但完全没有必要，还会降低代码可读性，下标变量直接用普通int类型存储即可。

修复方案 #

• 计算分段中点时增加边界截断：const int m = std::min(par + merge_sz, end);
• 移除合并循环中冗余的边界判断（sub_end本身已经和end取过最小值，p2 < sub_end已经隐含p2 < end）
• 去掉所有不必要的const引用绑定，下标变量直接使用普通int类型

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