自底向上归并排序在2^n+1大小的数据集上是否性能会比较差？
来源：3-4 自底向上的归并排序算法
慕运维2948618
2022-04-03
在递归实现中，都是在中间进行划分的。
但是在迭代实现中，都是等间距的。如果数据集大小为2^n + 1，那在最后一次归并排序中，左半部分就是2^n，右半部分就是1，此时归并就相当于是插入操作了。我记得老师说自底向上的归并排序会比递归实现慢一点，是否是这个原因呢？
我没有写代码测试，希望老师指点一下，谢谢~
写回答
1回答
-
从递归的层数来讲，自顶向下和自底向上是一样的。
比如 9 个元素（2^3 + 1）
用自底向上划分从 1 1 1 1 1 1 1 1 1 （9 个 1）开始
然后归并为 2 2 2 2 1
然后归并为 4 4 1
然后归并为 8 1
然后是 9，总共 5 层
用自顶向下划分，从 9 开始
然后划分为 4 5
然后划分为 2 2 3 2
然后划分为 1 1 1 1 2 1 1 1
然后划分为 1 1 1 1 1 1 1 1 1 ，也是 5 层。
自底向上 有的时候会慢一些的核心原因是，一些归并排序的优化在自底向上的时候没有作用。
比如如果发现左半部分的最大值比右半部分的最小值还要小的时候，那么当前处理的整个部分都可以不再处理了。这就可以大大削减整个归并排序的递归树，但是在自底向上的归并排序的过程中，整棵递归树一定会被遍历到，没有这个削减的空间。
但是这种优化都是常数级，或者对特殊测试数据的优化，并不改变整个归并排序的时间复杂度。而且由于在一些“特殊”的环境下，使用递归是一个性能的 concern（比如嵌入式开发中），所以自底向上的归并排序也是非常有意义的（虽然在这种情况下，使用希尔排序更常见一些。）
继续加油！：）
172022-11-16
相似问题
自底向上的归并排序的java代码问题
回答 1
为何有递归的自顶向下的排序方法要快？
回答 2