C语言归并排序实现的内存泄漏及二次释放错误排查求助

问题原因 #

出现double free的核心是内存所有权混乱：你在递归中释放的left_sorted或right_sorted指针，要么是上层递归还在依赖的内存，要么是最终返回的排序结果指针被重复释放了。

常见错误场景：

• 递归返回的最终排序结果数组，被你在递归内部free了一次，之后主函数又对同一个指针执行free操作。
• merge函数中复用了left_sorted或right_sorted的内存空间，导致后续对这些指针的free操作，实际上释放的是已被合并后数组占用的内存，后续再次操作时触发重复释放。

解决方法 #

1. 明确内存所有权规则 #

归并排序的内存管理要遵循谁分配，谁释放：递归层只负责释放自己分配的子数组内存，最终的排序结果由调用者负责释放。

2. 修正后的递归逻辑示例 #

以下是符合内存安全的归并排序实现框架：

#include <stdlib.h>
#include <string.h>
#include <stdio.h>

int* merge(int* left, int left_len, int* right, int right_len) {
    int* merged = malloc((left_len + right_len) * sizeof(int));
    int i = 0, j = 0, k = 0;
    while (i < left_len && j < right_len) {
        merged[k++] = (left[i] <= right[j]) ? left[i++] : right[j++];
    }
    memcpy(merged + k, left + i, (left_len - i) * sizeof(int));
    memcpy(merged + k + (left_len - i), right + j, (right_len - j) * sizeof(int));
    return merged;
}

int* merge_sort(int* arr, int len) {
    if (len <= 1) {
        // 长度为1时，分配新内存并复制元素，返回新指针
        int* res = malloc(len * sizeof(int));
        memcpy(res, arr, len * sizeof(int));
        return res;
    }

    int mid = len / 2;
    int* left_sorted = merge_sort(arr, mid);
    int* right_sorted = merge_sort(arr + mid, len - mid);

    int* merged = merge(left_sorted, mid, right_sorted, len - mid);

    // 释放当前递归层分配的左右子数组内存，上层无需再使用它们
    free(left_sorted);
    free(right_sorted);

    return merged;
}

int main() {
    int arr[] = {5, 2, 9, 1, 5, 6};
    int len = sizeof(arr) / sizeof(arr[0]);
    int* sorted_arr = merge_sort(arr, len);

    // 使用排序后的数组
    for (int i = 0; i < len; i++) {
        printf("%d ", sorted_arr[i]);
    }
    printf("\n");

    // 仅释放最终的排序结果，递归内部已处理子数组的释放
    free(sorted_arr);
    return 0;
}

3. 排查技巧 #

• 使用Valgrind的valgrind --leak-check=full --track-origins=yes ./your_program命令，定位double free的具体指针地址和调用栈，精准找到重复释放的位置。
• 在每个malloc和free处添加打印语句，记录指针地址，对比哪些地址被执行了多次free。

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