C 中具有百万值的 MergeSort 分段错误

Question

MergeSort 算法在插入一百万个元素的记录时出现分段故障错误，最多 300k 个值排序没有问题。 数据结构作为输入给出，并且基于我尝试进行的尝试，我认为这不是内存问题

void merge_sort(void *a, int left, int mid, int right, int size) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    char left_array[n1 * size];
    char right_array[n2 * size];  

    char *arr = (char *)a;

   



}

void merge(void* a, int left, int elem, int size) {
    if(left < elem){
        int mid = left + (elem - left)/2;
        merge(a, left, elem, size);
        merge(a, mid + 1, elem, size);
        merge_sort(a, left, mid, elem-1, size);
    }

}

我分配了尽可能多的内存但它似乎不是内存问题

Answer 1

快速解释

char left_array[len1 * size];
char right_array[len2 * size];

在这些行中，您分配了大约四百万字节（约 4Gb）的内存。这个内存是在栈上分配的，栈的一个特点就是不能无限增长，有上限。 Windows 上的默认堆栈大小为 1Mb，而在 Linux 上为 2Mb。

崩溃的原因 - 访问堆栈边界之外的内存。所以如果你想解决这个问题，你可能想要分配这个内存而不是在堆栈上，分配更少的内存，或者使堆栈更大。因为这显然是一个测试代码，所以我假设扩大堆栈是一个可以接受的解决方案，尽管在这种情况下，您分配的内存量非常大，因此在堆上分配它们可能更好。

可以使用

malloc

函数在堆上分配内存，使用情况可以上网查。这是最简单的，也可能是最好的解决方案。