algorithm - 自下而上合并排序在哪里有用？

Question

我一直在阅读 Sedgewick & Wayne 的“算法，第 4 版”。本书介绍了两种使用归并排序的方法。使用标准自顶向下递归合并排序或自底向上合并排序。

是否存在自下而上合并排序优于自上而下版本的情况？

Answer 1

递归合并排序需要O(log n)递归堆栈的空间，但自下而上的版本可以让你做得更好（没有递归堆栈，只有几个整数跟踪你在输入中的位置）。

如果您遇到一些不支持递归的语言并且只为您提供有限的堆栈内存（可能是嵌入式系统？），那么自下而上的版本将是您唯一的选择。

这是一个自下而上的版本，说明了我的意思。

Answer 2

自下而上的归并排序几乎可以在没有内存的情况下工作，被排序的数据保存在外部设备（例如磁带）上。我认为它在 50 年代和 60 年代曾经是这样工作的，我们在老电影中看到的那些高大的磁带机。

换句话说，自底向上合并是一种在线算法。它可以在根本没有随机访问的情况下工作。

我们首先处理输入磁带，并在读取输入磁带时分别写出 2 个元素的排序块，写入两个磁带，在两者之间交替写入。然后我们从刚刚写入的两个磁带中读取 2 个块，并写出合并的 4 个块，同时在输出磁带之间交替。然后我们再次切换输入和输出，并以 8 块为单位进行，等等。在最后一次运行中，只有一个磁带被写入 - 这就是结果。

这可以在只有 O(1) 额外内存的现代 RAM 硬件上进行仿真，并就地完成合并。为了处理“短悬尾”问题（对于像2^n+k，对于小的长度k），沿着输入序列的扫描可以交替地向前或向后方向进行。

Answer 3

具有相同的复杂性，只有很小的差异，例如它进行合并的顺序。递归的为左上右上，自下而上为水平。递归有时也会使其速度变慢，而且我认为不太直观。