在许多情况下，快速排序优于归并排序。但什么时候归并排序会比快速排序更好？
例如，当所有数据不能一次加载到内存时，归并排序的效果更好。还有其他情况吗？
suggested duplicate question 的答案列出使用快速排序优于合并排序的优点。我在询问合并排序比快速排序更好的可能情况和应用程序。
最佳答案
如果您不能一次将所有数据放入内存，则快速排序和归并排序都可以正常工作。您可以通过选择一个枢轴来实现快速排序，然后将元素从磁盘流式传输到内存中，并根据元素与枢轴的比较将元素写入两个不同文件之一。如果您使用双端优先级队列，您实际上可以通过一次将最大数量的可能元素装入内存来更有效地做到这一点。
归并排序是最坏情况下的 O(n log n)。也就是说，您可以轻松修改快速排序以生成 introsort。算法，快速排序、插入排序和堆排序的混合体，这是最坏情况下的 O(n log n)，但在大多数情况下保持快速排序的速度。
了解为什么快速排序通常比归并排序更快可能会有所帮助，因为如果您理解其中的原因，您可以很快找到归并排序明显胜出的某些情况。快速排序通常优于归并排序，原因有二:
Quicksort 比 mergesort 具有更好的引用局部性，这意味着在 quicksort 中执行的访问通常比 mergesort 中的相应访问更快。
Quicksort 使用最坏情况下的 O(log n) 内存(如果正确实现)，而归并排序由于合并开销需要 O(n) 内存。
不过，在一种情况下，这些优势会消失。假设您要对元素的链表进行排序。链表元素分散在整个内存中，因此优势 (1) 消失了(没有引用的位置)。其次，链表合并时只需O(1)的空间开销，而不是O(n)的空间开销，所以优势(2)消失了。因此，您通常会发现 mergesort 是一种用于对链表进行排序的高级算法，因为它进行的总比较次数较少，并且不易受到糟糕的主元选择的影响。
关于algorithm - 什么时候合并排序优先于快速排序？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/29218440/