C 语言归并排序如何按数组长度分配缓冲区？

2026-11-04数据小许

结论

可以按数组长度分配缓冲区。C99 支持变长数组（VLA），例如 int buffer[size];。不过，这种数组占用栈空间，递归时每一层都会创建一个数组。也可以用 malloc 分配缓冲区，并让递归过程重复使用它。

原代码中的 half、m、n 和 buffer 尚未定义。下面的实现使用共享缓冲区：mergeSort 只分配一次，递归辅助函数负责拆分和合并数组。

实现示例

#include <stddef.h>
#include <stdlib.h>

static void mergeSortRange(int *array, int *buffer,
                           size_t begin, size_t end) {
    if (end - begin < 2) {
        return;
    }

    size_t mid = begin + (end - begin) / 2;
    mergeSortRange(array, buffer, begin, mid);
    mergeSortRange(array, buffer, mid, end);

    size_t left = begin;
    size_t right = mid;
    size_t out = begin;

    while (left < mid && right < end) {
        if (array[left] <= array[right]) {
            buffer[out++] = array[left++];
        } else {
            buffer[out++] = array[right++];
        }
    }

    while (left < mid) {
        buffer[out++] = array[left++];
    }
    while (right < end) {
        buffer[out++] = array[right++];
    }

    for (size_t i = begin; i < end; ++i) {
        array[i] = buffer[i];
    }
}

int mergeSort(int *array, size_t size) {
    if (size < 2) {
        return 1;
    }
    if (array == NULL) {
        return 0;
    }

    int *buffer = malloc(size * sizeof *buffer);
    if (buffer == NULL) {
        return 0;
    }

    mergeSortRange(array, buffer, 0, size);
    free(buffer);
    return 1;
}

可以在头文件中声明这个函数：

#ifndef MERGE_SORT_H
#define MERGE_SORT_H

#include <stddef.h>

int mergeSort(int *array, size_t size);

#endif

在 main 中调用 mergeSort，并处理内存分配失败的情况：

if (!mergeSort(array, SIZE)) {
    fprintf(stderr, "mergeSort failed\n");
    return 1;
}

主程序当前调用的是 quickSort(array, 0, SIZE)，而示例代码定义的是 mergeSort。要测试归并排序，需要改为调用 mergeSort(array, SIZE)，并确保编译时包含实现 mergeSort 的源文件。

变长数组的选择

如果使用支持 VLA 的 C 编译器，可以在函数内写 int buffer[size];。使用前要确保 size > 0，并留意数组过大或递归调用过深时可能耗尽栈空间。使用上面的 malloc 方案时，各递归层共用同一块缓冲区，完成后要调用 free。