C语言归并排序程序为何输出两个0？求技术解析

嘿，我来帮你拆解这个问题，以及怎么用你添加的x、y变量来搞定它！

问题到底出在哪？ #

你的代码跑出来有两个0，核心原因是没有处理非2的幂长度的数组，加上merge调用时强行把两个子数组长度都设为k，导致了内存越界，把calloc分配的初始0给带进来了：

• 你的测试数组大小是13（数一下元素：67,55,8,0,4,-5,37,7,4,2,9,1,-1一共13个），不是2的幂，但你的mergesort.c里那段if(n < m)的检查完全没用——当m翻倍到16时，循环m < n直接不成立，根本触发不了错误提示，代码硬着头皮继续处理。
• 每次合并时，你都默认两个子数组长度都是k，但最后一组的第二个子数组根本没那么多元素，比如当k=8时，最后一组第一个子数组从索引0开始是8个元素，第二个子数组从索引8开始只有5个元素，但你还是按8个来处理，访问了超出数组范围的内存（这部分内存是calloc初始化的0），结果就把0写到了排序后的数组里。

用x、y变量修复的具体步骤 #

你已经加了x、y变量，我们就用它们来存两个子数组的真实长度，而不是强行用k：

修改mergesort.c的核心逻辑 #

把原来的循环部分改成这样，注释里写清楚每一步的作用：

/* Mergesort: Use merge() to sort an array of size n. */
#include "mergesort.h"
void mergesort(int key[], int n)
{
    int j,k,m, *w;
    int x,y; // 用来存储两个待合并子数组的实际长度

    // 删掉那段错误的“数组必须是2的幂”检查——归并排序完全支持任意长度数组
    // 原来的if(n < m)那段直接移除

    // 分配足够存整个数组的空间，不要用m，用n！
    w = malloc(n * sizeof(int)); 
    assert(w != NULL); /* 检查内存分配是否成功 */

    for (m = 1; m < n; m *= 2) { // m是当前子数组的基础长度，每次翻倍
        for (j = 0; j < n; j += 2 * m) {
            // 计算第一个子数组的长度：最多m个，不能超过数组剩余元素数
            x = m;
            if (j + x > n) {
                x = n - j;
            }
            // 计算第二个子数组的长度：最多m个，不能超过剩下的元素数
            y = m;
            if (j + x + y > n) {
                y = n - (j + x);
            }

            // 如果第二个子数组有元素才合并，否则直接复制第一个子数组
            if (y > 0) {
                merge(key + j, key + j + x, w + j, x, y);
            } else {
                for (int i = 0; i < x; i++) {
                    w[j + i] = key[j + i];
                }
            }
        }
        // 把合并好的结果从临时空间w复制回原数组key
        for (j = 0; j < n; ++j) {
            key[j] = w[j];
        }
    }
    free(w);
}

额外的小修复点 #

• 原来的w = calloc(m, sizeof(int));是错的：m是逐步翻倍的，最后m可能小于n，导致临时空间不够存整个数组，改成malloc(n * sizeof(int))或者calloc(n, sizeof(int))才能确保空间足够。
• 删掉那段没用的“数组必须是2的幂”的检查，归并排序本来就支持任意长度的数组，不需要这个限制。

为什么这样改就没问题了？ #

• x和y会根据当前剩余的元素数动态计算两个子数组的真实长度，再也不会越界访问内存了。
• 当第二个子数组没有元素时（比如数组长度是奇数的最后一次合并），直接把第一个子数组复制到临时空间，避免无效的合并调用。

测试效果 #

用你的测试数组运行修改后的代码，输出会是正确的升序结果：
-5 -1 0 1 2 4 4 7 8 9 37 55 67，再也不会出现多余的0啦！

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