我在接受采访时被问到这个问题.他们都是O(nlogn),但大多数人使用Quicksort而不是Mergesort.这是为什么？
我们知道快速排序是最快的排序算法.
collections.sort使用合并排序算法而不是快速排序.但是Arrays.sort使用快速排序.
Collections.sort使用合并排序而不是快速排序的原因是什么？
我在论坛中阅读了以下内容:
合并排序对于链接列表等不可变数据结构非常有效
和
当数据存储在内存中时,快速排序通常比合并排序更快.但是,当数据集很大并且存储在外部设备(如硬盘驱动器)上时,合并排序在速度方面是明显的赢家.它最大限度地减少了外部驱动器的昂贵读取
和
在链表上操作时,合并排序只需要少量的辅助存储
有人能帮助我理解上述论点吗？为什么合并排序首选排序庞大的链表？它如何最大限度地减少对外部驱动器的昂贵读取？基本上我想了解为什么会选择合并排序来排序大链表.