我一直在阅读Sedgewick和Wayne的《算法，第四版》。这本书介绍了两种使用归并排序的方法。使用标准的自顶向下递归归并排序或者自底向上归并排序。
是否有任何情况下自底向上归并排序比自顶向下版本更可取？
自下而上的归并排序在哪些情况下有用？
6
- Nikunj Banka
4
1https://dev59.com/y2kw5IYBdhLWcg3wE2dA - Mitch Wheat
2@MitchWheat 这个问题讨论的是两种排序算法的分析，而不是应用程序。 - Nikunj Banka
1你根据复杂性分析来选择应用程序！哈哈！ - Mitch Wheat
2两种算法的复杂度都相同（O(nlogn)）。这就是为什么要问这个问题。有没有特定的情况，自底向上更适合或不适合？ - Nikunj Banka
3个回答
9
递归归并排序需要O(log n)的递归栈空间，但底部向上版本让您可以做得更好（没有递归栈，只需几个整数来跟踪输入中的位置）。
如果您遇到一些不支持递归且仅提供有限内存用于堆栈（例如嵌入式系统）的语言，则底部向上版本将是您唯一的选择。
这里有一个底部向上版本，展示了我的意思。
- user541686
2
不完全正确...在通常的“均匀成本”模型中，我们假设可以将包含问题大小n的整数存储在O(1)内存中，自底向上的归并排序只需要O(1)空间。也可以（实际上更精确，但更繁琐）使用“对数成本”模型，其中空间以实际位数而不是足够大的整数来衡量，在这种情况下，自底向上的归并排序需要O(log n)空间（任何使用数组访问读取其完整输入的算法都需要O(log n)空间！），但在这个模型中，递归归并排序需要O(log^2 n)空间。 - j_random_hacker
@j_random_hacker：抱歉，你说得完全正确...由于某种原因，我认为跟踪输入位置需要O(log log N)位，我的错；感谢你指出来。 - user541686
2
底部合并排序可以在几乎没有内存的情况下工作，排序数据被保存在外部设备（例如磁带）上。我认为这就是50年代和60年代它是如何工作的，使用那些我们在老电影中看到的高大的磁带机器。
换句话说，自底向上的归并是一种在线算法。它可以在完全没有随机访问的情况下工作。
我们首先处理输入磁带，并将每个包含2个元素的已排序块写入两个磁带中，交替进行。然后我们从刚刚写入的两个磁带中按块读取2个元素，并写出合并的4个元素块，同时在输出磁带之间交替进行。然后我们再次切换输入和输出，并按块8个元素进行处理，以此类推。在最后一次运行中，只有一个磁带被写入 - 这就是结果。
这可以在现代RAM硬件上模拟，只需要O(1)的额外内存，而归并则在原地完成。为了处理“短悬挂尾”问题（对于像2^n+k这样的长度，对于小的k），可以沿着输入序列交替向前或向后进行扫描。
换句话说，自底向上的归并是一种在线算法。它可以在完全没有随机访问的情况下工作。
我们首先处理输入磁带，并将每个包含2个元素的已排序块写入两个磁带中，交替进行。然后我们从刚刚写入的两个磁带中按块读取2个元素，并写出合并的4个元素块，同时在输出磁带之间交替进行。然后我们再次切换输入和输出，并按块8个元素进行处理，以此类推。在最后一次运行中，只有一个磁带被写入 - 这就是结果。
这可以在现代RAM硬件上模拟，只需要O(1)的额外内存，而归并则在原地完成。为了处理“短悬挂尾”问题（对于像2^n+k这样的长度，对于小的k），可以沿着输入序列交替向前或向后进行扫描。
- Will Ness
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接