何时使用归并排序而不是快速排序？

Question

在许多情况下，快速排序比归并排序更好。但是，在什么情况下归并排序可能比快速排序更好呢？

例如，当所有数据无法一次性加载到内存中时，归并排序的效果更好。还有其他情况吗？

建议重复问题的答案列出了使用快速排序优于归并排序的优点。我正在询问可能的情况和应用程序，其中归并排序比快速排序更好。

- Mohamed Taher Alrefaie

Answer 1

快速排序和归并排序在无法一次性将所有数据装入内存时均可正常工作。您可以通过选择一个枢轴，然后从磁盘流式传输元素到内存，并根据该元素与枢轴的比较结果将元素写入两个不同的文件中来实现快速排序。如果使用双端优先队列，您甚至可以更有效地将最大数量的可能元素一次性装入内存中。

归并排序的最坏情况时间复杂度为 O(n log n)。话虽如此，您可以轻松修改快速排序以生成introsort算法，它是快速排序、插入排序和堆排序的混合体，最坏情况下的时间复杂度为 O(n log n)，但在大多数情况下保持了快速排序的速度。

了解为什么快速排序通常比归并排序更快可能会有所帮助，因为如果您理解原因，就可以很快找到一些情况，其中归并排序是明显的胜者。快速排序通常比归并排序更好，原因有两个：

1. 快速排序比归并排序具有更好的引用局部性，这意味着在快速排序中执行的访问通常比归并排序中对应的访问更快。

2. 如果实现正确，快速排序使用最坏情况下 O(log n) 的内存，而归并排序由于合并的开销需要 O(n) 的内存。

然而，有一种情况下这些优点会消失。假设您想要对元素的链表进行排序。链表元素分散在内存中，因此优势（1）消失了（没有引用局部性）。其次，可以仅使用 O(1) 的空间开销合并链接列表，而不是 O(n) 的空间开销，因此优势（2）消失了。因此，通常您会发现归并排序是对于链表排序的更优算法，因为它进行的总比较较少，并且不容易受到糟糕的主元选择的影响。

- templatetypedef

---

此外，归并排序通常是一种原地排序算法，在按列标题排序时非常有用。 - xpda

@xpda 这是错误的！大多数归并排序的实现具有O(n)的空间复杂度，因此它不是原地排序算法。虽然也有可以原地排序的实现，但它们要么不稳定，要么会增加性能复杂度。参考：https://en.wikipedia.org/wiki/Merge_sort - Alan Evangelista

快速排序的最坏情况空间复杂度是O(n)，而不是O(log n)。考虑使用快速排序对已排序的数组进行排序，但没有随机选择枢轴。 - roulette01

@roulette01 快速排序有一个标准的优化方法，即尾递归消除。不要进行两个递归调用，而是在两个子数组中较小的那个上发起递归调用，然后重复使用当前堆栈帧的空间来处理较大的子数组。由于每个新递归调用中处理的子数组大小最多是前一个子数组大小的一半，因此总使用的空间为O(log n)。 - templatetypedef

@templatetypedef 哦，我不知道那个。 - roulette01

Answer 2

相比快速排序，归并排序最重要的优势在于它的稳定性：比较相等的元素保留其原始顺序。

- user58697

Answer 3

1. MergeSort 是稳定的排序算法，相同元素保持原始顺序。
2. MergeSort 很适合并行实现（多线程）。
3. MergeSort 的比较次数比 QuickSort 少约30％。这是一个经常被忽视的优点，因为比较操作可能会很昂贵（例如在比较数据库行的多个字段时）。

- martinstoeckli

---

你能提供第2和第3个问题的来源吗？此外，快速排序也适用于多线程吗？ - Samuel Bushi

@blumonkey - 我自己编写了源代码，这是C#中的并行归并排序实现。很少有问题可以像这个算法一样被更好地分成独立的子任务。关于比较，维基百科上有相同的信息，并且它与我的测试结果相符。 - martinstoeckli

另一个关于2的来源是Thomas H. Cormen等人所著的《算法导论》第三版。书中有一个完整的章节，详细解释了如何实现多线程版本的归并排序。该章节为27.3节，位于第797页。 - Alberto Casas Ortiz

Answer 4

快速排序的平均情况是O(n log n)，但最差情况为O(n^2)。归并排序始终是O(n log n)。除了渐近最坏情况和归并排序的内存负载外，我想不到其他原因。

快速排序比归并排序更差的场景：

1. 数组已经排序好了。 2. 数组中所有元素都相同。 3. 数组按相反顺序排序。

如果您对数据一无所知，请选择归并排序而非快速排序。

- erip

---

对于场景#1和#3，这取决于您如何选择枢轴。几乎所有常见的实现都使用三数中值法来避免这两种情况。最坏情况仍然是O(n^2)，但没有简单的模式可以达到那种情况。有相同数量的模式，只是它们不是简单的。 - Mooing Duck

Answer 5

归并排序的时间复杂度保证在O(N log₂N)内。快速排序也有这样的限制，但它要高得多——是O(N²)。当您需要对代码的时间性能有保障时，请使用归并排序而不是快速排序。

例如，如果您为实时系统编写依赖于排序的代码，那么归并排序将是更好的选择。

- Sergey Kalinichenko

Answer 6

1. Merge Sort（归并排序）的最坏时间复杂度为O(nlogn)，而Quick Sort（快速排序）的最坏时间复杂度为O(n^2)。
2. Merge Sort是一种稳定排序算法，这意味着数组中相同元素之间的相对位置不会改变。

- Shantam Mittal

---

这个问题已经在其他答案中回答过多次了。 - ABCD