归并排序数组长度超过500000 程序就崩溃

Question

IDE是CLion,在测试归并排序n<=500000正常，超过程序就崩溃了，不知道是什么原因

Answer 1

liuyubobobo 2017-05-18 12:56:11

在我的课程中，在merge中使用 T aux[r-l+1]; 的方式来开辟辅助数组，是遵守变量在哪里使用，就在哪里定义的软件工程的原则。但是在实际上，如果数据量太大，这样做的缺点是占用了大量的系统栈空间。如果在小一些数据量的情况，你的归并排序是没有问题，相信是遭遇了这种情况。

最简单地解决方案，是将T aux[r-l+1];这样的辅助空间的开辟换做是使用new来进行开辟。我在github上的代码将使用new的方式申请空间打上了注释，请参考：https://github.com/liuyubobobo/Play-with-Algorithms/blob/master/03-Sorting-Advance/Course%20Code%20(C%2B%2B)/03-Merge-Sort-Advance/MergeSort.h

另外，对于大数据量的使用归并排序，有一个很重要的优化方案，就是将归并排序过程所需要使用的辅助空间，一次性在递归调用前全部开辟，之后一参数的形式传给递归过程以及merge辅助函数。我的github上对于这一章的补充代码展示了这个方法，如果有兴趣可以参考：https://github.com/liuyubobobo/Play-with-Algorithms/blob/master/03-Sorting-Advance/Course%20Code%20(C%2B%2B)/Optional-01-MergeSort-Create-aux-Array-Out-of-Merge/MergeSort2.h

• 提问者 青山烟雨青衫客 #1

  非常感谢！

• 提问者 青山烟雨青衫客 #2

  有个问题还需要请教下您，关于至下而上的归并排序的问题，变量sz在课程中说是merge元素的个数，比如第一轮sz=1,是不是merge的是2个元素，然后左右各1个元素，这样第一轮中，如果int数组8个元素，那就是每2个元素一次归并，共4次，第二轮sz=2,merge的是4个元素，左右各2个元素，共2次，第三轮sz=8,merge的是8个元素，也就是全部，左右个4个，共1次，不知我的理解有没有问题？请老师指正。

• liuyubobobo 回复 提问者 青山烟雨青衫客 #3

  完全正确哦：）

Answer 2

提问者 青山烟雨青衫客 2017-05-20 02:08:35

嗯，我明白了，谢谢，栈空间系统中是有限制，而用new的方式是开辟了堆空间，就不会有此问题了。