自底向上归并排序在2^n+1大小的数据集上是否性能会比较差？

Question

在递归实现中，都是在中间进行划分的。
但是在迭代实现中，都是等间距的。如果数据集大小为2^n + 1，那在最后一次归并排序中，左半部分就是2^n，右半部分就是1，此时归并就相当于是插入操作了。我记得老师说自底向上的归并排序会比递归实现慢一点，是否是这个原因呢？
我没有写代码测试，希望老师指点一下，谢谢~

Answer 1

liuyubobobo 2022-04-04 02:00:03

从递归的层数来讲，自顶向下和自底向上是一样的。

比如 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（比如嵌入式开发中），所以自底向上的归并排序也是非常有意义的（虽然在这种情况下，使用希尔排序更常见一些。）

继续加油！：）

• 提问者 慕运维2948618 #1

  非常感谢！

• 提问者 慕运维2948618 #2

  为什么在嵌入式开发使用希尔排序比较多呢？我记得您说过希尔排序的时间复杂度是O(n^(3/2))。如果是内存少，不使用递归的写法不就行了吗？

• liuyubobobo 回复 提问者 慕运维2948618 #3

  因为实现极度简单，并且在一般的数据规模，速度非常快。即使比归并排序慢一点，也完全在可接受的范围里。时间复杂度只是一个看当数据规模变化的情况下，数据增长趋势的工具，时间复杂度高，不一定性能一定高；时间复杂度差，不一定性能一定差，比如我们在归并优化中，会使用插入排序，就是这个道理。

点开查看后面4条评论