为什么在 C 中实现 merge sort 时调用 malloc 会导致程序崩溃？

2026-11-04排障赵师傅

复制右半部分时，newarr2 的下标用错了，导致堆内存越界写入。这可能破坏堆内存，使程序直到后续调用 malloc 时才崩溃。因此，调试器停在 malloc，不代表错误就发生在那里。

右半部分的分配长度也无法处理奇数，打印指针时使用的格式不正确。修复这些内存问题后，还需要补上归并排序的合并过程。

越界发生在哪里？

问题出在 sort_desassemble 的这段代码：

int *newarr2 = malloc(HALF * sizeof(int));

for (int i = HALF; i < len; i++)
{
    *(newarr2 + i) = *(arr + i);
}

以第一次调用的 len = 8 为例：

HALF 为 4。
newarr2 只分配了 4 个 int，合法下标是 0 到 3。
循环却写入 newarr2[4] 到 newarr2[7]，全部越界。

源数组应从 arr[4] 开始读取，目标数组则应从 newarr2[0] 开始写入。对应的赋值语句应改为：

newarr2[i - HALF] = arr[i];

C 不会自动检查数组边界。越界写入属于未定义行为，可能立即导致崩溃，也可能破坏分配器的管理信息，直到下一次调用 malloc 或 free 时才暴露。仅凭这段代码，无法确定实际运行时破坏了哪一块内存。

同时修正右半部分的长度

原代码为左右两部分都分配了 len / 2 个元素。长度为奇数时，右半部分需要多一个元素，因此还要调整分配长度。

例如，len = 5 时，左边需要 2 个元素，右边需要 3 个。可以这样计算：

int firstln = len / 2;
int secondln = len - firstln;

下面的函数保留原名称 sort_desassemble，可以替换原实现。调用时要求 len >= 2，且 arr 指向至少包含 len 个有效元素的数组。

SplitP sort_desassemble(int *arr, int len)
{
    int firstln = len / 2;
    int secondln = len - firstln;

    int *newarr = malloc((size_t)firstln * sizeof *newarr);
    if (newarr == NULL)
    {
        fprintf(stderr, "Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }

    int *newarr2 = malloc((size_t)secondln * sizeof *newarr2);
    if (newarr2 == NULL)
    {
        free(newarr);
        fprintf(stderr, "Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }

    for (int i = 0; i < firstln; i++)
    {
        newarr[i] = arr[i];
    }

    for (int i = 0; i < secondln; i++)
    {
        newarr2[i] = arr[firstln + i];
    }

    SplitP value = {newarr, newarr2};
    return value;
}

两个复制循环都使用目标数组自己的下标，检查范围更直观。例如，i < secondln 与右半部分的分配长度一致。sizeof *newarr 表示指针所指的一个元素的大小，在这里与 sizeof(int) 相同。

示例在分配失败时直接结束程序。如果需要让调用者处理失败，可以改为返回错误状态。

代码中还需要修复哪些问题？

`printf` 把指针当成了整数

原代码：

printf("%i", *(singlep + i));

singlep 是一个指针数组，*(singlep + i) 等价于 singlep[i]，类型为 int *。%i 要求对应参数的类型为 int，这种类型不匹配会导致未定义行为。

要打印指针指向的整数，应写成：

printf("%i,", *singlep[i]);

使用前要确保 singlep[i] 已经赋值，并且它指向的内存仍然有效。要查看地址，则使用：

printf("%p\n", (void *)singlep[i]);

拆分完成后，还没有执行合并

当前 sort 只递归拆分数组，把单个元素的地址依次存入 singlep。它没有调用 sort_reassemble，也没有比较元素或将有序结果写回 arr。

所以，修复内存错误后，singlep 记录的仍是原数组的元素顺序。完整的归并排序需要在两次递归调用返回后，合并两个已经排好序的子数组。

`sort_reassemble` 的返回值和复制逻辑不正确

sort_reassemble 目前没有被调用，不是当前执行路径中崩溃的直接原因。将它接入排序流程前，需要修复以下问题：

return *arr; 只返回第一个元素，局部分配得到的地址随之丢失。要返回合并数组，应把声明和定义的返回类型都改为 int *，并使用 return arr;。调用者负责释放结果。
比较元素时使用了当前下标，写入时却使用 *left 或 *right，始终读取各自的第一个元素。应分别读取 left[leftindex] 和 right[rightindex]。
主循环在任意一侧耗尽时结束，之后还需要把另一侧剩余的元素复制到结果数组。

合并时可以用独立的写入下标 k，相等时优先取左边元素：

int k = 0;

while (leftindex < lenleft && rightindex < lenright)
{
    if (left[leftindex] <= right[rightindex])
    {
        arr[k++] = left[leftindex++];
    }
    else
    {
        arr[k++] = right[rightindex++];
    }
}

while (leftindex < lenleft)
{
    arr[k++] = left[leftindex++];
}

while (rightindex < lenright)
{
    arr[k++] = right[rightindex++];
}

这段代码应放在结果数组成功分配、两个读取下标初始化之后。

分配失败、递归边界和释放也要处理

main 中也要检查 malloc 的返回值，再向数组写入数据。分配失败会返回 NULL，继续解引用就会出错。

当前递归只处理 ln == 1。如果以后允许空数组，还需要处理 ln <= 0，否则传入 0 后递归无法终止。向固定大小的 singlep 写入前，要确保 validcount < LEN；重复调用排序时，也需要重新管理计数。

每次成功分配的内存，都要明确由谁调用 free 释放。只要还需要通过 singlep 读取元素，就不能提前释放它指向的内存。

如何定位这类错误？

先开启编译警告，帮助发现这里的 printf 参数类型错误：

clang -std=c11 -Wall -Wextra -Wpedantic -g merge_sort.c -o merge_sort

如果本机编译器和运行环境支持 AddressSanitizer，可以使用以下命令编译并运行：

clang -std=c11 -Wall -Wextra -Wpedantic -g -O1 \
    -fsanitize=address,undefined -fno-omit-frame-pointer \
    merge_sort.c -o merge_sort

./merge_sort

AddressSanitizer 可以帮助定位这类堆缓冲区越界，报告通常会包含非法访问的位置和相关内存的分配位置。先修复第一处报告的错误，再重新运行，因为后续错误可能是前一次越界造成的连锁反应。

调试时可以先用固定数组代替随机数，分别检查偶数长度、奇数长度、单元素和重复元素的情况。检查每个复制循环时，都核对分配的元素数量和目标下标的最大值。本例分配了 4 个元素，却从下标 4 开始写入，已经超出了合法范围。