algorithm - 为什么合并排序优先于快速排序来排序链表

Question

我在论坛上读到以下内容:

Merge sort is very efficient for immutable datastructures like linked lists

和

Quick sort is typically faster than merge sort when the data is stored in memory. However, when the data set is huge and is stored on external devices such as a hard drive, merge sort is the clear winner in terms of speed. It minimizes the expensive reads of the external drive

和

when operating on linked lists, merge sort only requires a small constant amount of auxiliary storage

谁能帮我理解上面的论点？为什么合并排序优先用于排序巨大的链表？以及它如何最大限度地减少对外部驱动器的昂贵读取？基本上我想了解为什么人们会选择归并排序来对大链表进行排序。

Answer 1

快速排序非常适合就地排序。特别是，大多数操作都可以根据交换数组中的元素对来定义。然而，要做到这一点，您通常使用两个指针(或索引等)“遍历”数组。一个从数组的开头开始，另一个从数组的结尾开始。然后两者都向中间移动(当它们相遇时你就完成了一个特定的分区步骤)。这对于文件来说是昂贵的，因为文件主要面向一个方向的阅读，从头到尾。从末尾开始向后寻找通常成本相对较高。

至少在其最简单的体现中，归并排序几乎是相反的。实现它的简单方法只需要从一个方向查看数据，但是涉及将数据分成两个独立的部分，对这些部分进行排序，然后将它们合并回一起。

使用链表，很容易在一个链表中获取(例如)交替元素，并操纵链接以从这些相同元素创建两个链表。对于数组，如果您愿意创建与原始数据一样大的副本，则重新排列元素以便交替元素进入单独的数组很容易，但在其他方面则更重要。

同样，如果您将源数组中的元素按顺序合并到一个包含数据的新数组中，则与数组的合并会很容易——但是在不创建数据的全新副本的情况下就地进行合并是一个完全不同的故事。使用链接列表，将两个源列表中的元素合并到一个目标列表中是微不足道的——同样，您只需操作链接，而无需复制元素。

至于使用 Quicksort 为外部合并排序生成已排序的运行，它确实有效，但它通常(肯定)不是最优的。要优化合并排序，您通常希望在生成时最大化每个排序“运行”的长度。如果您只是读入适合内存的数据，对其进行快速排序并将其写出，则每次运行将被限制为(略小于)可用内存的大小。

不过，通常情况下，您可以做得更好。您从读取一个数据 block 开始，但不是在其上使用快速排序，而是构建一个堆。然后，当您将每个项目从堆中写出到排序的“运行”文件中时，您从输入文件中读取了另一个 项目。如果它比您刚写入磁盘的项目大，则将其插入现有堆中，然后重复。

较小的项目(即属于已写入项目之前的项目)保持分开，并构建到第二个堆中。当(且仅当)您的第一个堆为空，并且第二个堆已接管所有内存时，您停止将项目写入现有的“运行”文件，并开始一个新的。

具体效果如何取决于数据的初始顺序。在最坏的情况下(输入以相反的顺序排序)它根本没有用。在最好的情况下(输入已经排序)，它可以让您在一次输入中“排序”数据。在一般情况下(以随机顺序输入)，它可以让您将每次排序运行的长度大约增加一倍，这通常会将速度提高 大约 20-25%(尽管百分比会根据大多少而有所不同)你的数据比可用内存小)。