algorithm - 归并排序有哪些不同类型？

Question

我一直在阅读有关合并排序的文章，到目前为止我已经看到了三个主要的不同版本:

1. abstract in-place (顺便说一句，为什么这被称为“就地”，而实际上却不是？)
2. top-down
3. bottom-up

首先，为什么它们都被认为是同一个算法？是因为主要思想是将两个排序列表合并为一个排序列表吗？

其次，什么时候应该用哪个？就地抽象不会进行递归调用，我听说这是一件好事，因为它避免了深层调用堆栈(例如，我看到人们竭尽全力实现没有递归的快速排序)。这是否意味着就地抽象使用最少的内存？

TL;DR 抽象就地、自上而下和自下而上归并排序之间有什么区别？

Answer 1

这里有个小误区:abstract in-place merge不是mergesort，它是把两个数组合并在一起的套路。您的链接描述的两种风格是自下而上和自上而下的归并排序。它们是完全相同的算法，完全相同的比较和交换完成。但是实现依赖于每个不同的方法，这就是他们名字的由来。

抽象就地合并

归并排序的问题是执行它需要额外的空间。使它到位的所有方案都非常复杂且不太实用。这个方案只是一个好的就地归并排序的抽象，并且这个归并的实现很容易。但它不是就地的，并且仍然使用这个额外的 O(n) 内存。

自上而下的合并排序

这是最常见的一种。它通常依赖于递归，并使用自上而下的方法。即:从长度为 n 的数组开始，对两半进行递归排序，然后将它们合并在一起。我们称它为自上而下，因为我们从一个长度为 n 的数组开始，然后减少问题，直到我们得到一个大小为 1 的数组。

自下而上的合并排序

mergesort 的第二种变体，迭代工作。顾名思义，它使用自下而上的方法。这个直觉很简单:合并所有大小为 1 的子数组，然后合并所有大小为 2 的子数组，然后所有大小为 4 的子数组，依此类推，直到合并整个数组。

性能

mergesort 的两个变体具有相同的运行时间，因为操作完全相同。区别在于实现。一种是迭代，另一种是递归。我想人们对哪个更容易理解有自己的偏好。

关于调用堆栈的大小，没有什么可担心的。 top-down mergesort的调用栈不能超过log n，很少。最好避免深度调用堆栈，如果数据已经排序，这种情况可能会在快速排序中发生，但在合并排序中永远不会发生。