什么排序技术在合并时使用合并排序

Question

在合并排序的最后一个步骤中，我们有两个排序列表，我们试图将它们组合成一个排序列表，逻辑将如何去？

这就是我的天真头脑想出来的： 将列表＃1的每个元素与列表＃2的每个元素进行比较，并在列表＃2中找到它的位置。基本上就像插入排序。

但显然这不是如何发生，因为这给了我一个复杂的O（n^2）。 但合并排序是O（nlogn）。那么最后一步怎么样？

Answer 1

它使用合并排序。合并排序没有单独的排序算法，它是一种排序算法。

因此，您的原始列表已经排序，所以最小的元素总是在开始。比较A和B.取两者中的较小者并将其添加到结果列表的末尾。重复，直到两个源列表都为空。

Answer 2

这很大程度上取决于您如何构建您正在排序的数据。

合并排序通常主要用于外部排序，如排序磁盘上的文件。在这种情况下，您通常会从一些输入文件中获取输入，并将结果写入单独的输出文件。

如果你正在排序链表，你通常会做同样的事情 - 拿N个输入列表并产生一个输出列表。既然可以通过操作链接将元素从一个列表移动到另一个列表，这不需要（太多）额外的存储空间或时间。

你真的好像在问排序数组。如果你想在原地合并排序数组，是 a couple of algorithms已知，但它们有点不重要。

[我不喜欢只用链接到什么我猜是这里真正的答案，但的算法真的是有点多，试图勾勒甚至这里]