java - 适合内存的顺序数据的 QuickSort 和 MergeSort 性能与磁盘上访问顺序数据的速度比较慢

Question

以下引自《与其他排序算法的比较》 来自 Wikipedia Merge Sort 的部分页

On typical modern architectures, efficient quicksort implementations generally outperform mergesort for sorting RAM-based arrays.[citation needed] On the other hand, merge sort is a stable sort and is more efficient at handling slow-to-access sequential media.

我的问题:

1. 当要排序的数据都可以放入内存时，为什么 Quicksort 的性能优于 Mergesort？如果所有需要的数据都缓存或在内存中，那么快速排序和归并排序访问起来不是很快吗？

2. 为什么 Mergesort 在处理访问速度慢的顺序数据时更有效(例如在要排序的数据不能全部放入内存的情况下从磁盘处理数据)？

3. (从我下面的评论移至此处)在 n 个元素的基元数组 arr 中(数据是连续的)。 MergeSort 中必须读取和比较的一对元素是 arr[0] 和 arr[n/2](发生在最终合并中)。现在认为在 QuickSort 中必须读取和比较的一对元素是 arr[1] 和 arr[n](发生在第一个分区中，假设我们交换随机选择第一个元素的枢轴)。我们知道数据是按 block 读取的，然后加载到缓存中，或者从磁盘加载到内存(如果我错了请纠正我)，那么在使用 MergeSort 时，是否有更好的机会将所需数据一起加载到一个 block 中？ 在我看来，MergeSort 总是占上风，因为它可能会比较靠得更近的元素。我知道这是错误的(见下图)，因为 QuickSort 显然更快......我知道 MergeSort 不合适并且需要额外的内存，这可能会减慢速度。除此之外，我的分析还缺少哪些部分？

图片来自Princeton CS MergeSort and QuickSort slides

---

我的动机:

我想理解以上这些概念，因为它们是为什么在排序 LinkedList 或非顺序数据时首选 mergeSort 而在排序 Array 或顺序数据时首选 quickSort 的主要原因之一。以及为什么 mergeSort 在 Java 中用于对 Object 进行排序，而 quickSort 在 java 中用于对基本类型进行排序。

更新:Java 7 API实际上使用TimSort对Object进行排序，它是MergeSort和InsertionSort的混合体。对于原语 Dual-Pivot QuickSort。这些更改是从 Java SE 7 开始实现的。这与排序算法的稳定性有关。 Why does Java's Arrays.sort method use two different sorting algorithms for different types?

---

编辑:

如果您能回答以下几个方面，我将不胜感激:

• 我知道这两种排序算法在移动次数、读取次数和比较次数上有所不同。如果这些是导致我在问题中看到的行为的原因(我怀疑它)，那么将非常感谢对排序算法的步骤和过程如何导致它具有从磁盘或内存中寻找数据的优点或缺点的详尽解释.
• 欢迎提供示例。我通过示例学得更好。

---

注意:如果您正在阅读@rcgldr 的回答。在聊天室中查看我们的对话，其中有很多很好的解释和细节。 https://chat.stackoverflow.com/rooms/161554/discussion-between-rcgldr-and-oliver-koo

Answer 1

主要区别在于归并排序比快速排序执行更多移动，但比较次数更少。即使在对原生类型数组进行排序的情况下，快速排序也只快了 15% 左右，至少当我在伪随机 64 位无符号整数的大型数组上测试它时，这应该是快速排序的最佳情况，在我的系统(Intel 3770K 3.5ghz，Windows 7 Pro 64位，Visual Studio 2015，排序1600万伪随机64位无符号整数，快速排序1.32秒，合并排序1.55秒，1.32/1.55​​ ~= 0.85，所以快速排序是比归并排序快 15%)。我的测试是快速排序，没有检查以避免最坏情况 O(n^2) 时间或 O(n) 空间。由于检查被添加到快速排序以减少或防止最坏情况的行为(比如如果递归变得太深则回退到堆排序)，速度优势降低到不到 10%(这是我在 VS2015 的 std 实现之间得到的差异: :sort(改进的快速排序)与 std::stable_sort(改进的合并排序)。

如果对“字符串”进行排序，则被排序的更有可能是指向这些字符串的指针(或引用)数组。这是合并排序更快的地方，因为移动涉及指针，而比较涉及字符串的间接级别和比较。

选择快速排序而不是归并排序的主要原因不是速度，而是空间要求。合并排序通常使用与原始数组大小相同的第二个数组。快速排序和自上而下合并排序也需要 log(n) 个堆栈帧进行递归，对于快速排序，将堆栈空间限制为 log(n) 个堆栈帧是通过仅在较小的分区上递归，然后循环回处理较大的分区来完成的.

就缓存问题而言，最新的处理器有 4 路或 8 路关联缓存。对于合并排序，在合并期间，两个输入运行将在 2 个缓存行中结束，一个输出运行在第 3 个缓存行中。快速排序在进行交换之前扫描数据，因此扫描的数据将在缓存中，但如果要比较/交换的两个元素彼此之间的距离足够远，则扫描数据将在不同的行中。

---

对于外部排序，使用自下而上归并排序的一些变体。这是因为合并排序合并操作是顺序的(唯一的随机访问发生在启动一对新的运行时)，这在硬盘驱动器的情况下是快速的，或者在旧时代，磁带驱动器(至少需要 3 个磁带驱动器) ).每次读取或写入都可以针对非常大的数据 block ，从而减少硬盘驱动器中每个元素的平均访问时间，因为每次 I/O 都会同时读取或写入大量元素。

还应注意，库中的大多数归并排序也是自下而上归并排序的一些变体。自上而下的合并排序主要是一种教学环境实现。

---

如果在具有 16 个寄存器的处理器(例如 64 位模式下的 X86)上对 native 类型数组进行排序，其中 8 个寄存器用作 4 次运行的开始 + 结束指针(或引用)，则 4 路合并假设编译器将指针或引用优化为基于寄存器，排序通常与快速排序大致相同或快一点。这是一个类似的权衡，就像快速排序一样，4 向归并排序比传统的 2 向归并排序进行更多的比较(1.5 次比较)，但移动更少(0.5 次移动)。

---

应该注意的是，这些排序是 cpu 绑定(bind)的，而不是内存绑定(bind)的。我做了一个自底向上归并排序的多线程版本，在使用4个线程的情况下，排序快了3倍。使用 4 个线程链接到 Windows 示例代码:

https://codereview.stackexchange.com/questions/148025/multithreaded-bottom-up-merge-sort