为什么Merge sort用于Android/Java API中的对象？

Question

在Java中,基本类型的Arrays.sort()使用快速排序.另一方面,对象的Arrays.sort()使用Merge排序.同样适用于Collection.sort(),它也使用Merge排序.集合排序使用下面的Arrays排序实现.所以,简单来说,我可以说基元是使用快速排序排序的,但是对象是使用合并排序进行排序的.

我的猜测是它与自己的排序算法有关.关于快速排序vs合并排序的SO有很多讨论,像这样和这个.似乎存在相互冲突的主张哪个更好,这是可以理解的,因为这取决于数据集.

我的理解是

• 到位:快速排序获胜.可以在链接列表的就地实现合并排序
• 外部存储数据:合并排序获胜.
• 排序列表(由任何形式的链表支持):合并排序获胜.链接

Android API似乎遵循与Java相同的模式.这是我在Arrays.java中找到的

    public static void sort(long[] array) {
    DualPivotQuicksort.sort(array);
}

还有这个,

public static void sort(Object[] array) {
    ComparableTimSort.sort(array);
}

我不明白的是,是什么让Merge排序成为在Java或Android中排序对象的好选择？为什么不把这个决定留给开发者？

Answer 1

关键问题是排序稳定性 - 如果从排序顺序的角度看两个元素相等,它们是否以与输入中相同的顺序出现在结果中.

对于例如,这无关紧要long.3输入中的所有实例将组合在一起,没有人关心哪个是哪个.

另一方面,对象可能以不影响排序顺序的方式不同.如果您按腿数分类动物,您可能会关心"猫"和"狗"是否保持原始顺序.

该Arrays.sort归并排序是稳定的.用于基元的快速排序不需要稳定.