关于merge时copy的次序
bobo老师好，
在学习归并排序内存空间优化这一小节时，看到有一个将arr数组中元素拷贝到tmp数组的操作，在想为什么不是每次merge之后就将变化后的数据拷贝到tmp中来保持一致，因为从逻辑上来讲也是保证了arr变化后tmp的一致性。
修改测试后我发现，如果将拷贝这一操作放在每次merge之后，一样可以做到有序排列，但多次测试优化效果均不如merge方法一开始时copy的效果好。
我的理解是，如果每次merge完就直接拷贝会过于“敏感”而增加了拷贝的次数，而放在之前，根据递归的执行顺序，一些左右两部分排序后不需要merge的情况（左边的最大元素小于右边的最小元素），就跳过了本次的merge，也省去上次merge后立刻进行的的拷贝操作，到了后续更多元素的一次合并才触发了拷贝，进而使merge一开始来进行copy操作，比 merge后立刻拷贝保持一致的 效果更好。
您认为我这么理解对嘛？还是说这是其他的因素影响，比如数据样例或者机器性能等导致的？
正在回答
如果你后做 copy，相当于是为下一次 merge 做准备。但是，在最后一次 merge 以后，就没有下一次 merge 了，那么这次 copy 就白费了。你当然也可以加入一些 if 做判断要不要 copy，但是这样的 if 也是耗时的（因为在非最后一次 merge 的时候，都要做这个 if。）不管是从哪个角度，都会更耗时。
==========
更关键的是：merge 做的事情是：将两个有序数组，归并为一个有序数组。
之所以要做这次 copy，是为了完成上述目的。aux 数组的意义，是为了辅助这个过程。
如果你先做这次 copy，整个 merge 的函数语义完全可以忽视掉 merge 函数对 aux 的影响。因为在开始 merge 的时候，不管 aux 里存的是什么，都不影响。（在开始 merge 的时候，把 arr 里对应元素放到 aux 对应位置就好了。aux 就是一个辅助的空间而已。）
但是，如果你后做 copy，相当于 merge 的函数语义依赖于 aux 数组了。也就是 merge 函数的输入，不仅仅需要两个有序数组，还需要 aux 里准备好了这两个有序数组的 copy；而输出也不仅仅是一个有序数组，还包括对应在 aux 里的 copy，整个 merge 的函数语义变得更加复杂，输入依赖更多，输出需要检查的内容也更多（arr 和 aux 都变成了 merge 的输出。）
这个问题才是最致命的。因为如果你的实现正确的话，把 copy 改在后面对时间的影响是线性的，不会产生复杂度级别的变化。但是，整个函数的语义变得更复杂，可维护性变得极差。当然，这个问题不完全在这个课程讨论的范围里。
继续加油！：）
相似问题
登录后可查看更多问答，登录/注册
恭喜解决一个难题，获得1积分~
来为老师/同学的回答评分吧
0 星