归并排序的过程中数据为什么不会错乱？

Question

归并排序是一个不停归并交换的过程，但是归并的过程中并不是按照一定的有序顺序进行交换的，在数量级很大的情况下，交换不断进行，为什么不会发生错乱

Answer 1

liuyubobobo 2017-06-16 01:53:43

没有非常理解你的问题。你认为在归并的什么情况下会产生怎样的错乱呢？可否使用一个具体例子说明？

比如：你认为在具体什么情况下，按照你的逻辑理解，归并排序本应该“错误”的产生这个结果，可为什么实际却产生了正确的结果？

如果初次接触归并排序，确实很容易被其中的两次递归调用以及merge函数的关系搞晕。这种情况下，千万不要对着代码生想。强烈建议实际使用一个小数据量的测试用例，比如只包含8个元素的无序数组，然后使用debug一步一步跟着程序走一遍，观察程序在运行每一行代码之后数据和各种辅助的变量具体是怎样变化的，看看和自己的理解是否有偏差。这是非常好的理解算法运行机制的形式。千万不要怕麻烦！踏踏实实拿一张纸一根笔，找一个下午做一遍这个事情，是绝对值得的。

• 提问者 慕先生4311100 #1

  我看懂了，每一次递归执行完成后才会进行下一次递归

• 提问者 慕先生4311100 #2

  谢谢老师！