C语言百万级数据归并排序出现Segmentation Fault问题求助

核心问题分析 #

你的代码存在两个致命问题，直接导致百万级数据排序时触发段错误：

1. merge函数递归参数错误，引发无限递归
   看merge函数的递归调用：

   merge(a, left, elem, size);
   merge(a, mid + 1, elem, size);
   

   这里第一个递归调用的右边界应该是mid而不是elem，当前写法会让每次递归的右边界始终是初始的elem，导致递归无法收敛，形成无限递归。数据量较小时栈还没被耗尽，百万级数据会直接撑爆栈，触发Segmentation Fault。

   正确的递归调用应为：

   merge(a, left, mid, size);
   merge(a, mid + 1, elem, size);
   

2. 栈上分配大数组的风险
   merge_sort函数里用变长数组char left_array[n1 * size];和char right_array[n2 * size];，这类数组分配在栈上。栈的默认大小通常仅几MB到十几MB，处理百万级元素时，单次merge_sort分配的数组可能就占用数MB内存，叠加递归栈帧后极易超出栈容量，引发溢出。

   建议改用堆内存分配：

   char *left_array = malloc(n1 * size);
   char *right_array = malloc(n2 * size);
   // 使用完成后释放内存
   free(left_array);
   free(right_array);
   

补充说明 #

你提到排查后认为不是内存问题，但栈溢出属于内存问题的一种，且递归参数错误导致的无限递归是更直接的诱因。修正参数错误后，再将栈上数组改为堆分配，百万级数据排序即可正常运行。

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