千万级数组的MergeSort发生了溢出的解决方案
来源：3-2 归并排序法的实现
HuberyWang
2020-07-18
老师，我想问下您，对于如果需要排序的数组达到了千万的级别，应该怎么处理您所说的那个int数据类型不够使用的细节问题呢？
如图，我用的是vs code，一百万还没啥问题，一千万和五百万就出问题了。在网上找了关于segmentation fault报错原因就可能是内存溢出问题
写回答
3回答
-
这个溢出应该不是 int 型溢出的问题，而是每次都在 merge 中开空间导致的。解决方案是不要把临时空间放在 merge 中每次开空间，而是在 mergeSort 递归调用前统一开一次临时空间，以参数的形式传给 merge 使用。
具体可以参考这个课程我提供的补充代码：https://git.imooc.com/coding-71/coding-71/src/master/03-Sorting-Advance/Course%20Code%20%28C++%29/Optional-01-MergeSort-Create-aux-Array-Out-of-Merge/MergeSort2.h
注意注释的说明。
继续加油！：）
012020-07-19 -
HuberyWang
提问者
2020-07-18
写错了。应该是您说的(l+r)/2中l与r相加可能溢出的问题如何解决
00 -
HuberyWang
提问者
2020-07-18
是不是把int型改成long型呢
00
相似问题