如何用C语言的calloc实现支持任意长度数组的归并排序？

问题根源分析 #

现有代码存在三个核心问题：

• 仅处理长度为2k的数组段，完全忽略了数组末尾长度不足2k的剩余元素
• 调用merge时固定传入第二个数组长度为k，当剩余元素不足k时会触发越界访问，产生无意义的错误值（比如输出中的15）
• 每次外层循环后直接将整个w数组写回key，未区分已处理和未处理的元素区域，导致未排序的元素被错误覆盖

修改后的mergesort.c代码 #

#include "mergesort.h"

void mergesort(int key[], int n) {
    int j, k, len1, len2, *w;

    w = calloc(n, sizeof(int)); /* 分配工作空间 */
    assert(w != NULL);          /* 检查内存分配是否成功 */

    for (k = 1; k < n; k *= 2) {
        for (j = 0; j < n; j += 2 * k) {
            len1 = k;
            // 动态计算第二个子数组的实际长度，避免越界
            len2 = (j + k < n) ? k : n - (j + k);
            
            if (j + k >= n) {
                // 只剩单个子数组，直接复制到工作空间
                for (int i = 0; i < len1 && (j + i) < n; i++) {
                    w[j + i] = key[j + i];
                }
            } else {
                merge(key + j, key + j + k, w + j, len1, len2);
            }
        }
        // 将本轮排序结果从工作空间写回原数组
        for (j = 0; j < n; ++j) {
            key[j] = w[j];
        }
    }

    free(w); /* 释放工作空间 */
}

关键修改点说明 #

• 动态计算子数组长度：不再固定第二个子数组长度为k，而是根据剩余元素数量计算len2，彻底避免越界访问
• 处理末尾剩余元素：当遍历到数组末尾只剩单个子数组时，直接将元素复制到工作空间，确保所有元素都被纳入处理流程
• 修正循环遍历逻辑：内层循环条件改为j < n，保证能遍历到数组的所有元素段

验证结果 #

修改后运行原main.c，将输出正确的排序结果：

Before mergesort:
4    3    1   67   55    8    0    4   -5   37    7    4    2   9    1
After mergesort:
-5    0    1    1    2    3    4    4    4    7    8    9   37   55   67

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