C语言归并排序（Merge Sort）实现失效，请求排查问题

我仔细检查了你的C语言归并排序实现，发现几个核心问题导致排序结果异常，下面逐一分析并给出修复方案：

问题1：Merge函数中修改了参数指针，破坏边界判断 #

你的merge函数直接使用参数a和b作为遍历指针，在循环中执行a++和b++，导致后续判断子数组是否遍历完成的条件失效。比如原本b是右子数组的起始索引，循环后b的值被修改，while(a<b)这个判断左子数组剩余元素的条件就完全错误了。

问题2：归并逻辑颠倒（升序/降序搞反） #

你在合并时的判断条件是if(A[a] > A[b]) T[c++] = A[a++];，这会把更大的元素优先放入临时数组，如果目标是升序排序，这个逻辑完全颠倒了，应该优先放入更小的元素。

问题3：内存泄漏风险 #

每次调用merge都用malloc分配了临时数组T，但没有对应的free操作，会导致程序运行时内存泄漏。

修复后的完整代码 #

修正后的merge_sort函数（逻辑正确，无需修改） #

void merge_sort(int A[], int i, int j) {
    if(i < j) {
        int n = j - i + 1;
        int k = n / 2;
        merge_sort(A, i, i + k - 1);
        merge_sort(A, i + k, j);
        merge(A, i, i + k, j);
    }
}

修正后的merge函数 #

void merge(int A[], int a, int b, int j) {
    // 用临时变量保存左右子数组的遍历指针，避免修改原参数
    int left_ptr = a;
    int right_ptr = b;
    // 只分配当前合并所需的内存大小，而非整个数组长度
    int* T = malloc(sizeof(int) * (j - a + 1));
    int temp_idx = 0;

    // 合并两个有序子数组（升序）
    while (left_ptr < b && right_ptr <= j) {
        if (A[left_ptr] <= A[right_ptr]) {
            T[temp_idx++] = A[left_ptr++];
        } else {
            T[temp_idx++] = A[right_ptr++];
        }
    }

    // 处理左子数组剩余元素
    while (left_ptr < b) {
        T[temp_idx++] = A[left_ptr++];
    }

    // 处理右子数组剩余元素
    while (right_ptr <= j) {
        T[temp_idx++] = A[right_ptr++];
    }

    // 将临时数组元素复制回原数组
    temp_idx = 0;
    while (a <= j) {
        A[a++] = T[temp_idx++];
    }

    // 释放临时数组内存，避免泄漏
    free(T);
}

额外说明 #

• 确保DIM是你的数组实际长度，调用时merge_sort(A, 0, DIM-1)是正确的（因为数组索引从0开始）。
• 修复后，排序结果会变为正确的升序序列，同时解决了内存泄漏问题。

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