问为什么在对链表进行排序时，合并排序优于快速排序

EN

快速排序适用于就地排序。具体地说，大多数操作都可以通过交换数组中的元素对来定义。然而，要做到这一点，您通常使用两个指针(或索引等)“遍历”数组。一个从数组的开头开始，另一个从数组的末尾开始。然后，两者都朝着中间方向发展(当它们相遇时，您就完成了特定的分区步骤)。这对于文件来说是很昂贵的，因为文件从头到尾主要面向一个方向的读取。从最后开始并向后寻找通常是相对昂贵的。

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

使用链表，很容易获得(例如)一个链表中的交替元素，并操作这些链接以从这些相同的元素创建两个链表。对于数组，如果您愿意创建一个与原始数据一样大的副本，那么可以很容易地重新排列元素，以便将交替的元素放入单独的数组中，否则就会变得更加重要。

同样，如果您将源数组中的元素按顺序合并到一个新的数组中，那么使用数组合并也很容易--但是在不创建数据的全新副本的情况下就地合并则完全是另一回事。使用链表，将两个源列表中的元素合并到一个目标列表中非常简单--同样，您只需操作链接，而不复制元素。

至于使用快速排序为外部合并排序生成已排序的运行，它确实有效，但作为规则，它(显然)是次优的。为了优化合并排序，您通常希望在生成每个排序的"run“时最大化它的长度。如果您只是简单地读入适合内存大小的数据，快速排序并将其写出，则每次运行将被限制为(略小于)可用内存的大小。

不过，一般来说，您可以做得比这好得多。首先读取一个数据块，但不是对它使用快速排序，而是构建一个堆。然后，当您将每个项从堆中写出到排序的"run“文件中时，您将从输入文件中读入另一个项。如果它比您刚刚写入磁盘的项大，则将其插入到现有堆中，然后重复该操作。

较小的项(即，属于已经写入的项之前)要保持分离，并构建到第二个堆中。当(且仅当)第一个堆是空的，并且第二个堆占用了所有内存时，您停止将项目写入现有的"run“文件，并开始一个新的文件。

这究竟有多有效，取决于数据的初始顺序。在最坏的情况下(输入按逆序排序)，它一点好处都没有。在最好的情况下(输入已经排序)，它允许您在一次运行输入时对数据进行“排序”。在平均情况下(以随机顺序输入)，它可以让每次排序的运行长度大约增加一倍，这通常会将速度提高约20-25% (尽管百分比会根据数据比可用内存大小的不同而有所不同)。

快速排序依赖于能够索引到数组或类似的结构中。如果这是可能的，它很难击败快速排序。

但是你不能很快地直接索引到链表中。也就是说，如果myList是一个链表，那么如果可以编写这样的语法，那么myList[x]将涉及从列表的头部开始并跟随第一个x链接。对于快速排序进行的每个比较，都必须执行两次，这很快就会变得非常昂贵。

磁盘上也有同样的事情:快速排序将不得不查找和读取它想要比较的每一项。

合并排序在这些情况下速度更快，因为它按顺序读取项，通常使log2(N)遍历数据。所涉及的I/O要少得多，跟踪链表中的链接所花费的时间也少得多。

当数据适合内存并且可以直接寻址时，快速排序速度很快。Mergesort在数据无法装入内存或访问某个项目成本较高的情况下更快。

请注意，大文件排序通常会将文件尽可能多地加载到内存中，快速排序并将其写出到临时文件中，然后重复执行，直到遍历完整个文件。在这一点上，有一定数量的块，每个块都被排序，然后程序进行N路合并以产生排序的输出。

快速排序会将记录移到列表的中间。为了将一项移动到索引X，它必须从0开始并一次迭代一条记录。

合并排序将列表拆分成几个较小的列表，并且只比较列表头部的项。

合并排序的设置通常比快速排序所需的迭代操作开销更大。但是，当列表足够大，或者读取开销很大(比如从磁盘读取)时，快速排序迭代所需的时间将成为一个主要因素。