为什么Android/JavaAPI中的对象要使用归并排序？
Why Merge sort is used for objects in Android/Java API?
在Java Arrays.sort() for primitive type uses quick sort. On the other hand Arrays.sort() for objects uses Merge sort. And, same goes for Collection.sort()里面也用到了归并排序。集合排序在下面使用数组排序实现。因此，从简单的意义上讲，我可以说基元是使用快速排序进行排序的，而对象是使用合并排序进行排序的。
我的猜测是它与它自身的排序算法有关。关于 Quick sort vs Merge sort 的 SO 讨论很多，比如 this and this。关于哪个更好，似乎存在相互矛盾的说法，这是可以理解的，因为这取决于数据集。
我的理解是
- 到位：快速排序获胜。合并排序可以就地实现链表
- 外部存储数据：合并排序获胜。
- 排序列表（由任何形式的链表支持）：合并排序获胜。 Link
Android API 似乎遵循与 Java 相同的模式。这是我在 Arrays.java
中找到的
public static void sort(long[] array) {
DualPivotQuicksort.sort(array);
}
还有这个，
public static void sort(Object[] array) {
ComparableTimSort.sort(array);
}
我不明白的是，是什么让合并排序成为 Java 或 Android 中排序对象的良好候选者？为什么不把这个决定留给开发人员呢？
关键问题是排序稳定性 - 如果从排序顺序的角度来看两个元素相等，它们出现在结果中的顺序是否与输入中的顺序相同。
没关系，例如long。输入中 3 的所有实例将被组合在一起，没有人关心哪个是哪个。
另一方面，对象的不同可能不会影响排序顺序。如果您按腿数对动物进行排序，您可能会关心 "cat" 和 "dog" 是否保持原始顺序。
Arrays.sort 合并排序是稳定的。用于基元的快速排序不需要稳定。
归并排序是稳定的：相等的元素不会因为排序而重新排序
请看这个回答：Why Collections.sort uses merge sort instead of quicksort?
TL;DR:
QuickSort has two major deficiencies when compared to mergesort:
- It's not stable (as parsifal noted).
- It doesn't guarantee n log n performance; it can degrade to quadratic performance on pathological inputs.
我认为
的问题
what makes merge sort a good candidate for sorting Java objects and
quick sort that for primitives ?
别人已经回答了，但是
的问题
Why this decision has not been left to developers ?
尚未解决。
事实是，任何开发人员都可以轻松地从 Collection 或 ArrayList 和 hide 中派生出新的 class sort() 方法（因为 sort() 是一个 static 方法它必须是 hidden, not overidden）并使用自己的它的自定义实现。
很少（如果有的话）这样做的事实可能是因为当今大多数年轻程序员对 Java 的接触比对 C++ 的接触更多。在 Java 社区中，"abstraction" 意味着您不知道 class 的底层实现实际上是如何工作的，而且，您也不需要。 JVM 的机器独立性已经麻痹了我们对 speed/efficiency 权衡的直觉。因此，我们中的许多人对数据结构和算法的理解并不像一些年长且经验丰富的程序员那样清晰。
这和C++中对抽象的理解几乎是背道而驰的。引用 Alex Stepanov 的话：
As a matter of fact, I do not believe that a library could eliminate
the need for a programmer to know algorithms and data structures. It
only eliminates the need for a programmer to implement them. One needs
to understand the fundamental properties of data structures to use
them properly so that the application satisfies its own complexity
requirements.
在Java Arrays.sort() for primitive type uses quick sort. On the other hand Arrays.sort() for objects uses Merge sort. And, same goes for Collection.sort()里面也用到了归并排序。集合排序在下面使用数组排序实现。因此，从简单的意义上讲，我可以说基元是使用快速排序进行排序的，而对象是使用合并排序进行排序的。
我的猜测是它与它自身的排序算法有关。关于 Quick sort vs Merge sort 的 SO 讨论很多，比如 this and this。关于哪个更好，似乎存在相互矛盾的说法，这是可以理解的，因为这取决于数据集。
我的理解是
- 到位：快速排序获胜。合并排序可以就地实现链表
- 外部存储数据：合并排序获胜。
- 排序列表（由任何形式的链表支持）：合并排序获胜。 Link
Android API 似乎遵循与 Java 相同的模式。这是我在 Arrays.java
中找到的 public static void sort(long[] array) {
DualPivotQuicksort.sort(array);
}
还有这个，
public static void sort(Object[] array) {
ComparableTimSort.sort(array);
}
我不明白的是，是什么让合并排序成为 Java 或 Android 中排序对象的良好候选者？为什么不把这个决定留给开发人员呢？
关键问题是排序稳定性 - 如果从排序顺序的角度来看两个元素相等，它们出现在结果中的顺序是否与输入中的顺序相同。
没关系，例如long。输入中 3 的所有实例将被组合在一起，没有人关心哪个是哪个。
另一方面，对象的不同可能不会影响排序顺序。如果您按腿数对动物进行排序，您可能会关心 "cat" 和 "dog" 是否保持原始顺序。
Arrays.sort 合并排序是稳定的。用于基元的快速排序不需要稳定。
归并排序是稳定的：相等的元素不会因为排序而重新排序
请看这个回答：Why Collections.sort uses merge sort instead of quicksort?
TL;DR:
QuickSort has two major deficiencies when compared to mergesort:
- It's not stable (as parsifal noted).
- It doesn't guarantee n log n performance; it can degrade to quadratic performance on pathological inputs.
我认为
的问题what makes merge sort a good candidate for sorting Java objects and quick sort that for primitives ?
别人已经回答了，但是
的问题Why this decision has not been left to developers ?
尚未解决。
事实是，任何开发人员都可以轻松地从 Collection 或 ArrayList 和 hide 中派生出新的 class sort() 方法（因为 sort() 是一个 static 方法它必须是 hidden, not overidden）并使用自己的它的自定义实现。
很少（如果有的话）这样做的事实可能是因为当今大多数年轻程序员对 Java 的接触比对 C++ 的接触更多。在 Java 社区中，"abstraction" 意味着您不知道 class 的底层实现实际上是如何工作的，而且，您也不需要。 JVM 的机器独立性已经麻痹了我们对 speed/efficiency 权衡的直觉。因此，我们中的许多人对数据结构和算法的理解并不像一些年长且经验丰富的程序员那样清晰。
这和C++中对抽象的理解几乎是背道而驰的。引用 Alex Stepanov 的话：
As a matter of fact, I do not believe that a library could eliminate the need for a programmer to know algorithms and data structures. It only eliminates the need for a programmer to implement them. One needs to understand the fundamental properties of data structures to use them properly so that the application satisfies its own complexity requirements.