适合内存的顺序数据的 QuickSort 和 MergeSort 性能与磁盘上访问顺序数据的速度比较慢
QuickSort and MergeSort performance on Sequential data fit in memory vs Slow to Access Sequential data on disk
以下引自"Comparison with other sort algorithms"
来自 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.
我的问题：
当要排序的数据都可以放入内存时，为什么 Quicksort 优于 Mergesort？如果所有需要的数据都缓存或在内存中，那么 Quicksort 和 Mergesort 访问起来不是很快吗？
为什么 Mergesort 在处理访问速度慢的顺序数据（例如在要排序的数据不能全部放入内存的情况下从磁盘处理）时效率更高？
（从我下面的评论移到这里）在 n 个元素的原语数组 arr 中（数据是连续的）。 MergeSort 中必须读取和比较的一对元素是 arr[0] 和 arr[n/2]（发生在最终合并中）。现在认为在 QuickSort 中必须读取和比较的一对元素是 arr[1] 和 arr[n]（发生在第一个分区中，假设我们将随机选择的主元与第一个元素交换）。我们知道数据是按块读取的，然后加载到缓存中，或者从磁盘加载到内存（如果我错了请纠正我），那么在使用 MergeSort 时，是否有更好的机会将所需数据一起加载到一个块中？ 在我看来，MergeSort 总是占上风，因为它可能会比较靠得更近的元素。我知道这是 False（见下图），因为 QuickSort 显然更快......我知道 MergeSort 不合适并且需要额外的内存，这可能会减慢速度。除此之外，我的分析还缺少哪些部分？
图片来自Princeton CS MergeSort and QuickSort slides
我的动机：
我想了解以上这些概念，因为它们是为什么在排序 LinkedList 或 none 顺序数据时首选 mergeSort 而在排序 Array 或顺序数据时首选 quickSort 的主要原因之一。以及为什么在 Java 中使用 mergeSort 对 Object 进行排序，而在 java.
中使用 quickSort 对原始类型进行排序
update: 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.whosebug.com/rooms/161554/discussion-between-rcgldr-and-oliver-koo
主要区别在于归并排序比快速排序执行更多移动，但比较次数更少。即使在对原生类型数组进行排序的情况下，快速排序也只快了 15% 左右，至少当我在伪随机 64 位无符号整数的大型数组上测试它时，这应该是快速排序的最佳情况，在我的系统（Intel 3770K 3.5ghz，Windows7 Pro 64位，Visual Studio2015，排序1600万伪随机64位无符号整数，快速排序1.32秒，归并排序1.55秒，1.32/1.55~ = 0.85，所以快速排序比归并排序快 15%）。我的测试是快速排序，没有检查以避免最坏情况 O(n^2) 时间或 O(n) space。由于检查被添加到快速排序以减少或防止最坏情况的行为（比如如果递归变得太深则回退到堆排序），速度优势降低到不到 10%（这是我在 VS2015 的 [= 实现之间得到的差异） 34=]（修改后的快速排序）与 std::stable_sort（修改后的合并排序）。
如果排序 "strings"，被排序的更有可能是指向这些字符串的指针（或引用）数组。这是合并排序更快的地方，因为移动涉及指针，而比较涉及字符串的间接级别和比较。
选择快速排序而不是合并排序的主要原因不是速度，而是 space 要求。合并排序通常使用与原始数组大小相同的第二个数组。快速排序和自上而下合并排序也需要 log(n) 个堆栈帧进行递归，而对于快速排序，将堆栈 space 限制为 log(n) 个堆栈帧是通过仅在较小的分区上递归并循环回到处理更大的分区。
就缓存问题而言，最新的处理器具有 4 路或 8 路关联缓存。对于合并排序，在合并期间，两个输入 运行 将在 2 个缓存行中结束，一个输出 运行 在第 3 个缓存行中结束。快速排序在进行交换之前扫描数据，因此扫描的数据将在缓存中，但如果要比较/交换的两个元素彼此之间的距离足够远，则扫描数据将在不同的行中。
对于外部排序，使用自下而上合并排序的一些变体。这是因为合并排序合并操作是顺序的（唯一的随机访问发生在启动一对新的 运行s 时），这在硬盘驱动器的情况下是快速的，或者在旧时代，磁带驱动器（最少需要 3 个磁带机）。每次读取或写入都可以针对非常大的数据块，在硬盘驱动器的情况下减少每个元素的平均访问时间，因为每次读取或写入大量元素 I/O.
还应注意，库中的大多数合并排序也是自下而上合并排序的一些变体。自上而下的合并排序主要是一种教学环境实现。
如果在具有 16 个寄存器的处理器（例如 64 位模式下的 X86）上对本机类型数组进行排序，则其中的 8 个寄存器用作开始 + 结束指针（或引用）4 运行s ，那么假设编译器将指针或引用优化为基于寄存器的，则 4 路合并排序通常与快速排序大致相同或快一点。这是一个类似的权衡，就像快速排序一样，4 向归并排序比传统的 2 向归并排序进行更多的比较（1.5 x 比较），但移动更少（0.5 x 移动）。
应该注意，这些排序是 cpu 绑定的，而不是内存绑定的。我做了一个自底向上归并排序的多线程版本，在使用4个线程的情况下，排序快了3倍。 Link 到 Windows 使用 4 个线程的示例代码：
https://codereview.stackexchange.com/questions/148025/multithreaded-bottom-up-merge-sort
以下引自"Comparison with other sort algorithms" 来自 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.
我的问题：
当要排序的数据都可以放入内存时，为什么 Quicksort 优于 Mergesort？如果所有需要的数据都缓存或在内存中，那么 Quicksort 和 Mergesort 访问起来不是很快吗？
为什么 Mergesort 在处理访问速度慢的顺序数据（例如在要排序的数据不能全部放入内存的情况下从磁盘处理）时效率更高？
（从我下面的评论移到这里）在 n 个元素的原语数组
arr中（数据是连续的）。 MergeSort 中必须读取和比较的一对元素是arr[0]和arr[n/2]（发生在最终合并中）。现在认为在 QuickSort 中必须读取和比较的一对元素是arr[1]和arr[n]（发生在第一个分区中，假设我们将随机选择的主元与第一个元素交换）。我们知道数据是按块读取的，然后加载到缓存中，或者从磁盘加载到内存（如果我错了请纠正我），那么在使用 MergeSort 时，是否有更好的机会将所需数据一起加载到一个块中？ 在我看来，MergeSort 总是占上风，因为它可能会比较靠得更近的元素。我知道这是 False（见下图），因为 QuickSort 显然更快......我知道 MergeSort 不合适并且需要额外的内存，这可能会减慢速度。除此之外，我的分析还缺少哪些部分？
图片来自Princeton CS MergeSort and QuickSort slides
我的动机：
我想了解以上这些概念，因为它们是为什么在排序 LinkedList 或 none 顺序数据时首选 mergeSort 而在排序 Array 或顺序数据时首选 quickSort 的主要原因之一。以及为什么在 Java 中使用 mergeSort 对 Object 进行排序，而在 java.
中使用 quickSort 对原始类型进行排序update: 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.whosebug.com/rooms/161554/discussion-between-rcgldr-and-oliver-koo
主要区别在于归并排序比快速排序执行更多移动，但比较次数更少。即使在对原生类型数组进行排序的情况下，快速排序也只快了 15% 左右，至少当我在伪随机 64 位无符号整数的大型数组上测试它时，这应该是快速排序的最佳情况，在我的系统（Intel 3770K 3.5ghz，Windows7 Pro 64位，Visual Studio2015，排序1600万伪随机64位无符号整数，快速排序1.32秒，归并排序1.55秒，1.32/1.55~ = 0.85，所以快速排序比归并排序快 15%）。我的测试是快速排序，没有检查以避免最坏情况 O(n^2) 时间或 O(n) space。由于检查被添加到快速排序以减少或防止最坏情况的行为（比如如果递归变得太深则回退到堆排序），速度优势降低到不到 10%（这是我在 VS2015 的 [= 实现之间得到的差异） 34=]（修改后的快速排序）与 std::stable_sort（修改后的合并排序）。
如果排序 "strings"，被排序的更有可能是指向这些字符串的指针（或引用）数组。这是合并排序更快的地方，因为移动涉及指针，而比较涉及字符串的间接级别和比较。
选择快速排序而不是合并排序的主要原因不是速度，而是 space 要求。合并排序通常使用与原始数组大小相同的第二个数组。快速排序和自上而下合并排序也需要 log(n) 个堆栈帧进行递归，而对于快速排序，将堆栈 space 限制为 log(n) 个堆栈帧是通过仅在较小的分区上递归并循环回到处理更大的分区。
就缓存问题而言，最新的处理器具有 4 路或 8 路关联缓存。对于合并排序，在合并期间，两个输入 运行 将在 2 个缓存行中结束，一个输出 运行 在第 3 个缓存行中结束。快速排序在进行交换之前扫描数据，因此扫描的数据将在缓存中，但如果要比较/交换的两个元素彼此之间的距离足够远，则扫描数据将在不同的行中。
对于外部排序，使用自下而上合并排序的一些变体。这是因为合并排序合并操作是顺序的（唯一的随机访问发生在启动一对新的 运行s 时），这在硬盘驱动器的情况下是快速的，或者在旧时代，磁带驱动器（最少需要 3 个磁带机）。每次读取或写入都可以针对非常大的数据块，在硬盘驱动器的情况下减少每个元素的平均访问时间，因为每次读取或写入大量元素 I/O.
还应注意，库中的大多数合并排序也是自下而上合并排序的一些变体。自上而下的合并排序主要是一种教学环境实现。
如果在具有 16 个寄存器的处理器（例如 64 位模式下的 X86）上对本机类型数组进行排序，则其中的 8 个寄存器用作开始 + 结束指针（或引用）4 运行s ，那么假设编译器将指针或引用优化为基于寄存器的，则 4 路合并排序通常与快速排序大致相同或快一点。这是一个类似的权衡，就像快速排序一样，4 向归并排序比传统的 2 向归并排序进行更多的比较（1.5 x 比较），但移动更少（0.5 x 移动）。
应该注意，这些排序是 cpu 绑定的，而不是内存绑定的。我做了一个自底向上归并排序的多线程版本，在使用4个线程的情况下，排序快了3倍。 Link 到 Windows 使用 4 个线程的示例代码：
https://codereview.stackexchange.com/questions/148025/multithreaded-bottom-up-merge-sort