为什么合并排序用于Android / Java API中的对象？

Question

在Java中，原始类型的Arrays.sort（）使用快速排序。另一方面，对象的Arrays.sort（）使用合并排序。而且，同样使用Merge排序的Collection.sort（）也是如此。集合排序使用下面的数组排序实现。因此，从简单的意义上讲，我可以说基元是使用快速排序来排序的，而对象是使用合并排序来排序的。

我的猜测是它与自身的排序算法有关。上有快速的SO如此多的讨论排序VS归并排序，像这样和这个。似乎有相互矛盾的主张，哪一种更好，这是可以理解的，因为这取决于数据集。

我的理解是

• 到位：快速排序获胜。合并排序可以就地实现链接列表
• 外部存储数据：合并排序获胜。
• 排序列表（由任何形式的链接列表支持）：合并排序获胜。链接

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

关键问题是排序稳定性-如果从排序顺序的角度来看两个html" target="_blank">元素相等，那么它们在结果中的显示顺序是否与输入中的顺序相同。

例如没关系long。3输入中的所有实例将被分组在一起，没有人关心哪个是哪个。

另一方面，对象可能在不影响排序顺序的方式上有所不同。如果按腿数对动物进行分类，则可能会担心“猫”和“狗”是否保持原始顺序。

该Arrays.sort归并排序是稳定的。用于原语的快速排序不需要稳定。