顺序数据的QuickSort和MergeSort性能适合内存,慢速访问磁盘上的顺序数据

Question

以下引用来自Wikipedia Merge Sort页面中的"与其他排序算法的比较"部分

在典型的现代体系结构中,高效的快速排序实现通常优于mergesort,用于排序基于RAM的阵列.[citation needed]另一方面,合并排序是一种稳定的排序,在处理慢速访问顺序介质方面更有效.

我的问题:

1. 当要排序的数据全部适合内存时,为什么Quicksort的性能优于Mergesort？如果所需的所有数据都被缓存,或者内存中的Quicksort和Mergesort都不能快速访问？

2. 为什么Mergesort在处理缓慢访问的顺序数据方面更有效率(例如在要排序的数据不能全部适合内存的情况下从磁盘中)？

3. (从下面的评论转到此处)在arrn个元素的基元数组(数据是顺序的)中.必须在MergeSort中读取和比较的元素对是arr[0]和arr[n/2](在最终合并中发生).现在认为被读取并在快速排序相比是一对具有元件arr[1]和arr[n](在第一分区中发生时,假设我们交换与第一元件的随机选择的枢轴).我们知道数据是以块的形式读取并加载到缓存中,或者加载到磁盘到内存(如果我错了,请纠正我)那么使用MergeSort时所需的数据是否更有可能在一个块中加载？在我看来,MergeSort总是会有优势,因为它可能会比较更紧密的元素.我知道这是假的(见下图),因为QuickSort显然更快......我知道MergeSort不到位并需要额外的内存,这可能会减慢速度.除了我在分析中遗漏了哪些东西？

图像来自Princeton CS MergeSort和QuickSort幻灯片

---

我的动机:

我想理解上面这些概念,因为它们是为什么在排序LinkedList时首选mergeSort的主要原因之一,或者在排序数组或顺序数据时没有优先顺序数据和quickSort.为什么mergeSort用于在Java中对Object进行排序,而quickSort用于在java中对原始类型进行排序.

更新:Java 7 API实际上使用TimSort对Object进行排序,Object是MergeSort和InsertionSort的混合体.对于原语Dual-Pivot QuickSort.这些更改是从Java SE 7开始实现的.这与排序算法的稳定性有关.为什么Java的Arrays.sort方法对不同类型使用两种不同的排序算法？

---

编辑:

我将感谢一个解决以下方面的答案:

• 我知道两种排序算法在移动,读取和比较的数量上有所不同.如果那些原因导致了我在我的问题中列出的行为(我怀疑它),那么彻底解释排序算法的步骤和过程如何导致从磁盘或内存中寻找数据的优点或缺点将非常感激.
• 欢迎举例.我通过例子更好地学习.

---

注意:如果你正在阅读@ rcgldr的答案.看看我们在聊天室里的对话,它有很多很好的解释和细节.https://chat.stackoverflow.com/rooms/161554/discussion-between-rcgldr-and-oliver-koo

Answer 1

主要区别在于合并排序可以实现更多移动,但比快速排序更少.即使在对本机类型数组进行排序的情况下,快速排序的速度也只提高了约15%,至少当我在大型伪随机64位无符号整数数组上进行测试时,这应该是我的快速排序最好的情况.系统(英特尔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个磁带驱动器) ).每次读取或写入都可以用于非常大的数据块,从而减少了硬盘驱动器中每个元件的平均访问时间,因为每个I/O一次读取或写入大量元素.

还应该注意的是,库中的大多数合并排序也是自下而上合并排序的一些变体.自顶向下合并排序主要是教学环境实现.

如果在具有16个寄存器的处理器上对本机类型的数组进行排序,例如64位模式下的X86,其中8个寄存器用作4次运行的起始+结束指针(或引用),那么4路合并排序通常是假设编译器优化指针或基于寄存器的引用,那么与快速排序大致相同或稍快一些.这是一个类似的权衡,如快速排序,4路合并排序比传统的双向合并排序更多的比较(1.5 x比较),但更少的移动(0.5 x移动).

应该注意的是,这些排序是cpu绑定的,而不是内存绑定的.我创建了一个自下而上合并排序的多线程版本,在使用4个线程的情况下,排序速度提高了3倍.使用4个线程链接到Windows示例代码:

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