一起学习Collections.sort()中的Timsort-京东云开发者社区

### 1 引言
提到java.util.Collections大家肯定都比较熟悉，它是java工具包下的集合操作工具类，该类中抽取了集合操作的通用方法。这里主要来探讨一下它里面的排序方法Collections.sort()。排序功能作为一个开发者，在日常开发过程中随处可见，该方法相信大家也不会感到陌生。对于一个通用的排序算法，如果要去实现的话，会考虑使用什么样排序算法比较合适，在尽量降低时间、空间复杂度的情况下，又要兼顾保证稳定性，达到优秀的性能。可能从性能角度出发首先会想到的就是快速排序，或者归并排序。作为jdk提供的通用排序功能，使用如此频繁，肯定有独特之处，那它到底使用了什么神奇的算法来进行排序的呢？带着疑问来揭开它的面纱，在探索它高效的秘密的时候，同时也分析和对比一下它与其他大家熟知的排序算法的异同。

文中不会过多的介绍几大基本排序算法的方式、由来和思想，主要精力集中在一块探讨java中Collections.sort方法所使用的算法是如何排序的，以及哪些内容是值得我们学习和借鉴的。文中如有理解和介绍的错误，欢迎批评指正，共同学习进步。

### 2 Collections中sort方法介绍
输入Collections.sort，代码编辑器联想出来两种API，一种是两个参数可以根据比较策略排序的方法，另一种没有比较策略。两种API的都有入参为List<T>类型的list，本文主要以不带比较器的sort方法来探讨。

![](//img1.jcloudcs.com/developer.jdcloud.com/64819d0e-15b0-48a2-8591-36dd9087a74820210819140334.png)

以下为Collections类中关于sort方法定义

![](//img1.jcloudcs.com/developer.jdcloud.com/c68914a3-77bf-438b-9d39-79c58458b0f820210819140347.png)

通过该方法注释，查看到有三项值得关注的信息，大概意思是想表达该方法实现了稳定且默认升序排序的功能。
- Sorts the specified list into ascending order, according to the Comparable natural ordering of its elements.
- This sort is guaranteed to be stable equal elements will not be reordered as a result of the sort.
- The specified list must be modifiable, but need not be resizable.

进入sort，代码进入到List类的sort方法，发现方法将入参list先转为了数组Object[]，之后利用Arrays.sort进行排序。

![](//img1.jcloudcs.com/developer.jdcloud.com/4102fcf6-9dd6-45d1-8af0-622e8de2670520210819140414.png)

首先在这里思考一个问题为什么要转为数组，问题答案已经在方法的英文注释中说明白了。

![](//img1.jcloudcs.com/developer.jdcloud.com/789168fa-8ef5-4580-92cb-45384b54343b20210819140427.png)

是为了避免直接对List<T>的链表进行排序，从而耗费O(n2logn) 时间复杂度。当然这里在this.toArray()时，为了将list强行变为数组会损失一些性能和空间开销，源码中使用了System.arraycopy调用底层操作系统方法进行数据复制，详细内容可以查看相关实现。

继续进入Arrays类的sort方法定义中，我们没有使用比较器，LegacyMergeSort.userRequested表示进入老的归并排序算法，默认是关，直接进入本文重点关注的TimSort.sort(…)方法。

![](//img1.jcloudcs.com/developer.jdcloud.com/890b8f2a-f130-4f7f-b27e-37142abdbbda20210819140453.png)

### 3 TimSort算法介绍
Timsort是一个自适应的、混合的、稳定的排序算法，是由Tim Peter于2002年发明的，最早应用在Python中，现在广泛应用于Python、Java、Android 等语言与平台中，作为基础的排序算法使用。其中Java语言的Collection.sort在JDK1.6使用的是普通的归并排序，大家都知道归并排序虽然时间复杂度低，但是空间复杂度要求较高，所以从JDK1.7开始就更改为了TimSort算法。

Timsort 的时间复杂度是 O(n log n)，与归并排序的时间复杂度相同，那它的优势是啥呢，实际上可以认为TimSort排序算法是归并排序算法的优化版，从它的三个特征就可以看出，第二个特征“混合的”，没错，它不单纯是一种算法，而是融合了归并算法和二分插入排序算法的精髓，因此能够在排序性能上表现优异。其它两个特征自适应和稳定性会在文章后面讲到。首先从算法性能统计上做个对比：

![](//img1.jcloudcs.com/developer.jdcloud.com/dfa9d479-33f6-4423-9677-05ca889b36d420210819140530.png)

可以看出TimSort排序算法，平均和最坏时间复杂度是O(nlogn)，最好时间复杂度是O(n)，空间复杂度是O(n)，且稳定的一种排序算法。在稳定算法中，从性能效果上对比来看和二叉排序算法一样。
#### 3.1 TimSort的核心思想
那TimSort算法的核心思想是什么呢，首先原始的TimSort对于长度小于64的数据（java中是32），会直接选择二分插入排序，效率很高。其次，TimSort算法的初衷是认为现实中的数据总是部分有序的。这句话很关键，怎么理解呢，比如列表[5, 2, 8, 5, 7,23, 45, 63]，里面的[5, 2] 和 [8, 5] 和 [7, 23, 45,63] 各子列表中就是有序的，要么升序要么降序。这就是TimSort的基本根据，基于此会发现待排序列表已经部分有序了，所以会在排序过程中尽量不要破坏这种顺序，就可以做到减少排序时间消耗。基本思想说完了，由此引出TimSort算法的几个概念：run和minrun。

run是指连续升序或者连续降序的最长子序列（降序和升序可以相互转换），而minrun是一个设定值，实际上是每个run的长度最小值。所以TimSort会对待排序序列进行划分，找出连续有序的子序列，如果子序列长度不满足这点要求，就将后续数据插入到前面的子序列中。举个例子，待排序序列[5, 2, 8, 5, 7,23, 45, 63]， 如果minRun = 3，那分割后的run可能会有以下几个：[2, 5, 8]、[5,7,23,45,63] 两个子序列，最终通过合并这两个run得到[2,5,5,7,8,23,45,63]

是不是有个疑问： minrun怎么选择得到的？据算法介绍是通过大量的统计计算给出的minrun长度建议是在32 ~ 64之间取值效率比较高，具体在java代码中可能会有所不同。

接着来看，假设现在有序子序列已经拆分好了，该进入到合并过程中了，TimSort是如何合并子序列的。对于归并排序我们都知道，序列先归后并，两两组合利用一个空数组直接进行比较就合并了。但是在TimSort算法中，合并过程是实时的，每次算出一个run就可能做一次合并。这个过程利用了栈结构，且需要遵循相邻的run才可以合并，也就是只有相邻的栈元素可以进行合并。

规则如下：假设当前有三个run子序列依次入栈，现在栈顶有三个元素从上至下依次为x3、x2、x1，它们的长度只要满足以下两个条件中的任何一个就进行合并：

1. x1 <= x2 + x3
2. x1 <= x2

满足这个条件的三个序列，像汉诺塔一样长度由下往上依次减小。刚才提到合并run的过程是实时的，也就是每产生一个run就进行一次合并操作。举例说明下，当前假设待排序序列[2,6,8,4,2,5,7,9,10,11,4,25,64,32,78,99]，其中再假设minrun=3是合理的。合并过程是这样的，注意这里的压栈和弹栈不一定需要对子序列本身进行操作，不是真的将子序列放入栈中，而只需要run标识以及长度即可，因为栈元素比较的是run长度。

1. 首先第一个run0是[2,6,8]，而第二个run1是[2,4,5]，此时依次将其放入栈中，发现满足第二个条件，这两个run进行合并，合并后将旧序列从栈中弹出，得到新的run0是[2,2,4,5,6,8]，再次压入栈中。
2. 继续从原序列中找到新的run1是[7,9,10,11]，压入栈中，此时run0和run1不满足条件不需要合并。继续从原序列中找到run2是[4,25,64]，压入栈中，此时满足第一个条件，这里的run1和run2需要进行合并，合并后将旧序列从栈中弹出，新run1是[4,7,9,10,11,25,64]，压入栈中。
3. 此时发现run0和run1满足第二个条件，继续合并弹出旧序列，得到新run0是[2,2,4,4,5,6,7,8,9,10,11,25,64]，压入栈中。
4. 继续从原序列中找到新的run1是[32,78,99]，压入栈中。此时发现没有更多元素，而条件是不满足的，依然进行一次合并，弹出旧序列，压入合并后的新子序列run0是[2,2,4,4,5,6,7,8,9,10,11,25,32,64,78,99]
5. 此时将run0拷贝到原序列就完成了排序

![](//img1.jcloudcs.com/developer.jdcloud.com/b9b9a9ca-fcb6-424e-a636-c55884b8b3d620210819140703.png)

为什么要设置这么两个合并run的严格条件，直接压栈合并岂不更好？目的是为了避免一个较长的有序片段和一个较小的有序片段进行归并，在合并长度上做到均衡效率才高。

在合并run的过程中会用到一种所谓的gallop(飞奔)模式，能够减少参与归并的数据长度，主要过程如下：假设有待归并的子序列x和y，如果x的前n个元素都是比y首元素小的，那这n个元素实际上就不用参与归并了。原因就是这n个元素本来已经有序了，归并后还是在原来的位置。同理而言，如果y的最后几个元素都比x最后一个元素小，那y的最后这n个元素也就不必参与归并操作了，这样就可以减少归并长度，减少来回复制多余数据的开销。

#### 3.2 Java代码是如何实现的
探讨完TimSort的核心思想及其排序过程，现在来看下java代码是如何实现的。Java1.8中的TimSort类位置在java.util.TimSort

![](//img1.jcloudcs.com/developer.jdcloud.com/b9df6a6f-211a-46a9-a8b6-4f31347a56ea20210819140722.png)

变量nRemaining记录的是待排序列表中剩余元素个数， MIN_MERGE就是前文中提到的java中的minrun值是32。如果nRemaining<32，用countRunAndMakeAscending(…)方法得到连续升序的最大个数，里面涉及到升序降序调整。可以看到如果待排序列表小于32长度，就进行二分插入排序binarySort(…)。

如果待排序列表长度大于32，调用TimSort对象的minRunLength(nRemaining) 计算minRun，这里就体现了动态自适应，具体来看代码中是如何做的。r为取出长度n的二进制每次右移的一个溢出位值，n每次右移1位，直到长度n小于32。n+r最终结果就是保留长度n的二进制的高5位再加上1个移除位。根据注释可以看出：
- 如果待排序数组长度为2的n次幂，比如1024，则minRun = 32/2 = 16
- 其它情况的时候，逐位右移，直到找到介于16<=k<=32的值。

假如待排序列表长度是7680，二进制是1111000000000，按照操作后是11110十进制是30，再加上移除位0是30，所以minRun=30

![](//img1.jcloudcs.com/developer.jdcloud.com/3ea7fade-5d56-476b-b6ec-dd08f955104a20210819140837.png)

接下来在循环中进行处理：
1. 计算最小升序的run长度，如果小于minRun，使用二分插入排序将run的长度补充到minRun要求的长度
2. ts.pushRun(lo, runLen) ，通过栈记录每个run的长度，这里lo是run的第一个元素的索引用来标记操作的是哪个run，runLen是run的长度。
![](//img1.jcloudcs.com/developer.jdcloud.com/8f836689-04c7-48a1-9915-9be717798aa620210819140915.png)
3. ts.mergeCollapse(); 通过计算前面提到的两个run合并的限定条件，分别是：
 - runLen[n-1] <= runLen[n] + runLen[n+1]
 - runLen[n] <= runLen[n + 1]
![](//img1.jcloudcs.com/developer.jdcloud.com/888b8533-e9ee-4bff-8455-ec27b52c242720210819141012.png)
4. 这里的mergeAt(n) 归并排序过程，之前有提到是经过优化后的归并排序，具体表现在方法中的gallopRight和gallopLeft方法。
![](//img1.jcloudcs.com/developer.jdcloud.com/17e9f585-e079-492f-9e20-37e07cd6af1220210819141113.png)

假设有X序列[4,9,21,23]， Y序列[5,7,12,13,14,15,17]，由于X中4小于Y序列最小元素5，所以合并后4必然是第一个元素；而Y序列中尾元素17比X中的[21,23]小，所以X中的[21,23]必然是合并最后两元素。

至此，java版TimSort方法就介绍完毕了。

### 4 相同环境排序时间对比
想要真正模拟一模一样运行环境，是困难的。这里只是模拟相同的数据集，在相同机器上，其实就是平时办公的机器，统计不同排序算法排序过程中耗费的时间，这里的结果仅供参考。

模拟数据：随机得到1亿个范围在0到100000000内的整型元素构成数组，分别基于普通快速排序、普通归并排序、TimSort的排序算法得到耗时结果如下，单位ms

![](//img1.jcloudcs.com/developer.jdcloud.com/010a05e0-3f4b-40f0-8011-4dc242e1468320210819141154.png)

通过测试验证结果来看，在当前数据集规模下，TimSort的性能表现比较优异，当然此处测试结果仅供参考并不代表学术与研究性质。实际上如果待排序序列本身有序度高，TimSort的优势可能更加明显。需要明确的是不应该有假象认为TimSort就是最快的排序算法，比如像快速排序有很多的优化等，此处并没有考虑到其它优化算法的优异性能，对于这些相关的内容就不再做进一步的介绍与对比了。

### 5 总结与探讨
文中一起了解学习了TimSort算法的排序思想与java实现。它作为基本排序实现被广泛的应用，肯定有其值得学习与借鉴的地方。该算法是由二分插入排序和归并排序进行混合而成的算法，实际上平时很多使用的经典算法结构都不是一种类型或者一种方式，比如HashMap中随着数据量大小有链表与红黑树的转化，再比如Redis中的各种数据结构不都是一种实现。这些经典优秀的实现都用到了诸如此类的思想。

------------
自猿其说Tech-JDL京东物流技术发展部
作者：网规技术部 秦彪