C++归并排序处理10万元素栈溢出问题及修复方法咨询

问题描述 #

我正在编写程序对比两种排序算法的耗时、平均耗时，其中归并排序在数组大小为75000时能正常运行，但数组大小达到100000时出现栈溢出错误。以下是出错的归并排序代码片段：

//_______________________________
// MERGE SORT
void merge(int arr[], int l, int m, int r) {
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;
    /* create temp arrays */
    int L[100000], R[100000];
    /* Copy data to temp arrays L[] and R[] */
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];
    /* Merge the temp arrays back into arr[l..r]*/
    i = 0; // Initial index of first subarray
    j = 0; // Initial index of second subarray
    k = l; // Initial index of merged subarray
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    /* Copy the remaining elements of L[], if there are any */
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    /* Copy the remaining elements of R[], if there are any */
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}
/* l is for left index and r is right index of the sub-array of arr to be sorted */
void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        // Same as (l+r)/2, but avoids overflow for
        // large l and h
        int m = l + (r - l) / 2;
        // Sort first and second halves
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}
// END MERGE SORT
//_______________________________

插入排序部分无异常，请问该如何修复这个栈溢出问题？

问题分析 #

原因非常明确——栈空间被耗尽了：

• 你在merge函数里声明了两个固定大小为100000的int数组L和R，每个数组占100000 * 4字节 = 400KB，加起来就是800KB。而程序的栈空间通常很小（Windows默认1MB，Linux默认8MB左右），当处理100000大小的数组时，归并排序的递归调用会不断创建栈帧，再加上每个merge调用的大数组，很快就会把栈撑爆。
• 虽然归并排序的递归深度只有O(log n)（1e5的话大概17层），但叠加栈上的大数组，就触发了溢出。

修复方案：用动态内存分配替代栈上数组 #

最直接且安全的解决办法是从堆上分配临时数组，堆的空间远大于栈，不会轻易耗尽。修改后的merge函数如下：

void merge(int arr[], int l, int m, int r) {
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;
    
    // 只分配需要的大小，而不是固定100000，节省内存
    int *L = (int *)malloc(n1 * sizeof(int));
    int *R = (int *)malloc(n2 * sizeof(int));
    
    // 记得检查内存分配是否成功，避免空指针访问
    if (!L || !R) {
        fprintf(stderr, "内存分配失败，无法完成归并\n");
        exit(EXIT_FAILURE);
    }
    
    /* Copy data to temp arrays L[] and R[] */
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];
    
    /* Merge the temp arrays back into arr[l..r]*/
    i = 0;
    j = 0;
    k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    
    /* Copy remaining elements of L[] */
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    
    /* Copy remaining elements of R[] */
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
    
    // 使用完一定要释放内存，避免内存泄漏
    free(L);
    free(R);
}

额外优化建议 #

1. 预分配全局临时数组：如果觉得每次merge都malloc/free太耗时，可以提前分配一个和原数组大小相同的全局临时数组，在merge里复用它的不同区间。不过全局变量要注意线程安全，如果是单线程程序可以放心用。
2. 递归转迭代：如果想彻底避免递归栈的问题，可以把归并排序改成迭代版本，但这个改动较大，对于1e5的数组来说，上面的动态内存分配已经足够解决问题了。

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