Java 7是否使用Tim Sort作为Method Arrays.Sort？
我找不到Java 7的文档，我只能findJava 6，它仍然很快或合并。 有谁知道如何在Java 7中find方法Arrays.sort的文档？
Java 7对基元使用Dual-Pivot Quicksort，对对象使用TimSort。
根据基元的Java 7 API文档：
实现注意事项：sortingalgorithm是由Vladimir Yaroslavskiy，Jon Bentley和Joshua Bloch编写的Dual-Pivot Quicksort。 该algorithm在许多数据集上提供了O（n log（n））性能，这些数据集导致其他快速sorting降低到二次性能，并且通常比传统（单枢轴）Quicksort实现更快。
根据对象的Java 7 API文档：
这个实现是从Tim Peters的Python列表类（TimSort）改编的。 它使用Peter McIlroy的“Optimistic Sorting and Information Theoretic Complexity”中的技术，在Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms，第467-474页，1993年1月。
不知道这是否与Java 6有很大不同：
一个经过调整的quicksort，改编自Jon L. Bentley和M. Douglas McIlroy的“Engineering a Sort Function”，Software-Practice and Experience，Vol。 23（11）第1249-1265页（1993年11月）
是的，Java 7将为Arrays.sort使用Timsort。 这里是提交： http : //hg.openjdk.java.net/jdk7/jdk7/jdk/rev/bfd7abda8f79
是! …也没有。
概要
在当前的Open JDK 0实现中，Tim Sort通常用于sorting对象数组（ Arrays.sort(Object[])和朋友） – 但对于基本数组 （ Arrays.sort方法的其余部分），有多种方法，包括但不限于Tim Sort。 在这种情况下，启发式用来select使用哪种sorting方法。
对于原语，启发式根据所sorting的数据在各种sorting方法中进行select。 这些决定大部分是根据被sorting的数组的types和大小简单地进行的，但是对于int和long元素，决策实际上是基于测量的数组sorting的自适应。 所以在很多情况下，在适应/反思（TimSort）的基础上，你有适应/反省（启发式selectalgorithm）！
细节
Tim Sort用于大多数对象，例如Arrays.sort(Object[] a) ，除非用户通过将系统属性java.util.Arrays.useLegacyMergeSort设置为true来明确请求传统行为。
对于基元而言，情况更为复杂。 从JDK 8（版本1.8.0_111 ）开始，根据要sorting的数组的大小，基本types和测量的“sorting”来使用各种heurstics。 这里有一个概述：
- 对于除字节1以外的所有基本types，less于47个元素的数组仅使用插入sorting进行sorting（请参阅
DualPivotQuicksort.INSERTION_SORT_THRESHOLD）。 当使用合并或快速sorting并且子arrays的大小低于阈值时，对sorting的子数组也使用此阈值。 所以某种forms的插入sorting将被用于各种types，对于小型数组，这是唯一使用的algorithm。 - 对于原始types
byte，short和char， 计数sorting用于较大的数组。 这是一个简单的sorting，需要O(n + range)时间，其中range是字节总数（256）或short / char（65536）值。 这种sorting包括分配一个基本的range值数组，因此只有当要sorting的元素数量占整个范围的很大一部分时才使用它。 特别是用于大于29个元素的字节数组（即〜11％的范围）和大于3200个元素的短/字符数组（〜5％的范围）。 - 对于字节数组，总是使用上面两种方法中的一种。
- 对于高于插入sorting阈值的插入sorting阈值和
short/char数组，在插入sorting阈值以上和计数sorting阈值以下的int和long数组，可以使用两种algorithm之一：双枢轴快速sorting或合并sorting。 使用哪一个取决于数组sorting的度量：input被分为上升或下降元素的运行 。 如果这样的运行次数大于66，则该arrays被认为是大部分未sorting的，并且用双枢轴快速sorting进行sorting。 否则，数组被认为大部分被sorting，并且使用mergesort（使用已经枚举的运行作为起点）。
查找运行然后使用mergesort对它们进行sorting的想法实际上与timsort非常相似，尽pipe存在一些差异。 所以至less对于一些参数来说，JDK正在使用一个运行感知合并器，但是对于许多其他参数组合，它使用的是不同的algorithm，并且总共使用了至less4个不同的algorithm！
合理
Object[]与primitive之间不同sorting行为的原因可能至less有两方面：
1） Object[]sorting需要稳定 ：平均sorting的对象将以与input相同的顺序出现。 对于原始数组，不存在这样的概念：原语完全由它们的值定义，所以在稳定sorting和不稳定sorting之间没有区别。 这就允许原始sorting，而不需要稳定的algorithm来支持速度。
2） Object[]sorting需要涉及Object.compare()方法，这可能是任意复杂和昂贵的。 即使compare()方法很简单，通常会有方法调用开销，除非整个sorting方法可以内联2 。 所以， Object[]通常会偏向于最小化总体比较，即使以一些额外的algorithm复杂度为代价。
另一方面，原始数组的sorting只是直接比较通常需要一个或两个周期的原始值。 在这种情况下，考虑到比较的成本和周围的algorithm，algorithm应该被优化，因为它们可能具有相同的幅度。
0至less对于Java 7和Java 9之间的版本，当然这也包括Oracle的JDK，因为它基于Open JDK。 其他实现可能使用类似的方法，但我没有检查。
1对于字节数组，插入sorting阈值实际上是29个元素，因为这是使用计数sorting的较低截止值。
2这似乎不大可能，因为它相当大。
