源码解析Collections.sort ——从一个逃过单测的 bug 说起
本文从一个小明写的bug 开始，讲bug的发现、排查定位，并由此展开对涉及的算法进行图解分析和源码分析。
事情挺曲折的，因为小明的代码是有单测的，让小明更加笃定自己写的没问题。所以在排查的时候，也经历了前世的500年，去排查排序后的list改动（主要是小明和同事互相怀疑对方的代码，这里不多说了）。
本文从问题定位之后开始讲：
前言
小明写了一个自定义排序的代码，简化后如下。聪明的你快来帮小明review一下吧。
代码
背景：有一组商品，status是状态，其中2表示有货，9表示区域无货，5表示已抢光。需要按照 2 有货< 9 区域无货< 5 已抢光的顺序进行排序。
例如：输入：[2, 9, 5, 5, 9, 2, 9]，期望输出：[2, 2, 9, 9, 9, 5, 5]。list不为空，数量小于100。
环境：JDK 8
小明的代码如下：
/**
* 排序
*/
private static int compare(Integer status1, Integer status2) {
// 5大于9 大于2 ，按照这样的规则排序
if (status2 != null && status1 != null) {
// 5-已抢光, 已抢光排到最后面
if (status2.equals(5)) {
return -1;
} else {
// 9-区域无货, 区域无货排在倒数第二，仅在已抢光之前
if (status2.equals(9) && !status1.equals(5)) {
return -1;
}
}
}
return 0;
}
//Test
public static void main(String[] args) {
List list = Lists.newArrayList(2, 9, 5, 5, 9, 2, 9);
System.out.println("排序前:"+list);
list.sort(Test::compare);
System.out.println("排序后:"+list);
}
看上面的代码有问题么？别急，咱们先给个入参试一下。
测试
[ 2, 9, 5, 5, 9, 2, 9 ]
public static void main(String[] args) {
List list = Lists.newArrayList(2, 9, 5, 5, 9, 2, 9);
System.out.println("排序前:"+list);
list.sort(Test::compare);
System.out.println("排序后:"+list);
}
输出：
排序前:[2, 9, 5, 5, 9, 2, 9]
排序后:[2, 2, 9, 9, 9, 5, 5]
结论：结果是对的，符合预期 。 （ 按照 2 有货< 9 区域无货< 5 已抢光的顺序进行排序） 。
嗯，看起来排序是对的。但确实是有问题呢？
（小明OS ：哪里有问题？不可能有问题！我本地是好的！）
那我们看看情景复现👉🏻
情景复现
那有什么问题呢？我们再给几个入参试一下 。
case1 : 随机入参
[5, 9, 2, 5, 9, 9, 9, 5, 2]
输出：
排序前:[5, 9, 2, 5, 9, 9, 9, 5, 2]
排序后:[2, 2, 9, 9, 9, 9, 5, 5, 5]
期望是:[2, 2, 9, 9, 9, 9, 5, 5, 5]
结论：结果对，符合预期 ✅。
case2 : 多增加一些数
[2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 5, 5, 5, 5, 5, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 9, 5, 5]
输出：
结论：结果不对了，不符合预期 ❌。
case3 : 换几个数
[2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 9, 9, 9, 9, 9, 5, 5, 5, 5, 5, 9, 9, 9, 9, 5, 5]
输出：
结论：结果又对了？？
这是什么情况？!
小明有些慌了，越想越觉得奇怪，目前看起来有这样几个看起来些许离谱的结论：
1、可能是和数据量有关系（因为用32位以下的数据，多次Test 也没发现问题），
2、一定和数据数值有关系。（32位以上，有的数据样本没问题，有的有问题）。
3、有问题都在中间部分，而两边是有序的，猜测像排序归并导致的问题。
定位
想查这个问题，小明有三个思路。
一是：代码的逻辑比较，是有一些不完整的。那可以先试着改改代码，通过这几个失败用例，然后在找深层原因。
二是：查查用的排序类，有没有坑。用法有没有特殊注意的，有没有类似的案例。
三是：从源码上，理清排序底层的逻辑，找到哪一个环节排序出了问题。
顺着这三个思路，小明发现写的代码里缺少返回为1的场景。虽然小明不知道有没有影响，但是试了试，发现好使。。但为啥呢？
private static int compare(Integer status1, Integer status2) {
// 5大于9 大于2 ，按照这样的规则排序
if (status2 != null && status1 != null) {
// 5-已抢光, 已抢光排到最后面
if (status2.equals(5)) {
return -1;
} else {
// 9-区域无货, 区域无货排在倒数第二，仅在已抢光之前
if (status2.equals(9) && !status1.equals(5)) {
return -1;
}**else{
return 1;
}**
}
}
return 0;
}
然后小明看 Collections.sort 的坑，没有看到和这个相关的。
接下来，还是要来调试代码。最终定位是因为原来的compare 自定义代码里，对 compaer(5,2) 这种应该返回1的情况 ，默认返回了0。导致在底层两组数据归并排序过程，误以为5和2相等了。
即导致了这样错误的结果:
见Debug部分：（具体分析内容在后边源码部分）
解决方案
发现问题，就好解决了。方案是，要么补充完善逻辑，要么换用一种权重映射的排序方式。
1 优化代码
private static int compare(Integer status1, Integer status2) {
// 5大于9 大于2 ，按照这样的规则排序
if (status2 != null && status1 != null) {
// 5-已抢光, 已抢光排到最后面
if (status2.equals(5)) {
return -1;
} else {
// 9-区域无货, 区域无货排在倒数第二，仅在已抢光之前
if (status2.equals(9) && !status1.equals(5)) {
return -1;
}else{
return 1;
}
}
}
return 0;
}
2 改为权重等方式排序
当然，还有对于一些容易理解出错的排序，也可以通过设置权重映射的方式进行排序。
小明忽然想起来，无论底层排序算法是什么， 排序逻辑还是要完整。这一点也开发规约也是有的呀。 👉🏻
【注意】在JDK7版本及以上，为了让Arrays.sort、Collections.sort正常工作，Comparator必须满足以下三个条件，否则会抛出IllegalArgumentException异常。
1）比较x和y的结果应该与比较y和x的结果相反。
2）如果x>y，y>z，则x>z。
3）如果x=y，则比较x和z的结果应该与比较y和z的结果相同。
好了问题解决了，那我们接下来慢慢聊聊这里Collections.sort 底层用的TimSort排序原理。以及为什么32位及以上才有问题，为什么正好是归并过程有问题 ？
源码解读
JAVA 7 中集合类中的sort 开始，默认用TimSort排序方法 。Tim Sort，里的Tim 也没什么特别的含义。Tim是这个算法的创始人Tim Peters 的名字。该算法首先在Python中应用，之后在 java 中应用。
TimSort ：一种稳定的、自适应的、迭代的归并排序，在部分排序数组上运行时需要的比较远远少于nlg (n)次，而在随机数组上运行时提供与传统归并排序相当的性能。像所有合适的归并排序一样，这种排序是稳定的，运行时间为O(n log n)(最坏情况)。在最坏的情况下，这种排序需要n/2个对象引用的临时存储空间;在最好的情况下，它只需要少量的常量空间。这个实现改编自Tim Peters的Python列表排序
图解 TimSort 排序原理
如果数组的长度小于32，直接采用二分法插入排序。（略）
如果数组的长度大于32，找到 单调上升段（或下降段，进行反转），然后基于这个单调片段，通过插入排序的方式进行合并。如此反复归并相邻片段。
到这一步的时候，小明恍然大悟，怪不得32位数以下，没有出现过问题呢。
这个算法里有一个重要的概念，也可以理解为分段( 算法里 run )。每个分段都是连续上升或下降的子串
然后对下降的分段进行反转，使其变为一个递增的子串。这样就可以得到若干的分段，使得每个分段都单调递增，后续就可以对这些分段进行合并。
👉🏻 当然算法里会计算出一个最小的分段长度（Java里16-32之间），来控制分段的数量以保证效率。对那些不满足最小长度的分区，会采用二分插入的方法，使其满足最的长度。比如我们假设最小的长度是3，那此时由于第二段36 不符合最小长度3，会利用二分插入法，将8插入到第二段。即 368 就是第二段了。
分段划分之后，下一步就是如何进行合并。
合并时，会将分区进行压栈，并判断是否需要和之前的分段做合并。当然还有一些更详细的优化点，具体可看下文源码部分。重点说一下，两个分段如何进行合并。
假设以下内容：
第一个段包含元素：[1,2,3,5,6,8,9]
第二个段包含元素：[4,6,7,8,10,11,12]
第一个段在数组中出现在第二个段之前。请注意，实际段落长度不会这么短。如前所述，段落长度应介于16到32之间。此处只是提供示例以说明问题。
gallopRight()：查找第二个段的第一个元素在第一个段中的位置。例如，在此示例中，位置为2。这意味着前两个元素不需要参与合并，它们的位置不需要改变。
gallopLeft()：查找第一个段的最后一个元素在第二个段中的位置。在此处，发现第二个段中的第四个元素为10。因此，第二个段中的10、11、12不需要参与合并，它们的位置也不需要改变。
最终参与合并的段为：
第一段：[5，6，8，9]
第二段：[4, 6, 7, 8]
这样参与合并的段的长度就大大减小了。 这里就是我们上边问题出现的地方。在gallopLeft 方法里，
查找第一个段的最后一个元素【5】在第二个段中的位置时，比较【5】和【2】时，得出了相等的结果。这有什么影响呢？因为数组分段是单调递增的，也就是说第一组里最后一个（最大的）数据5，和第二组里第一个（最小的）数据2 相等。那也就是说，第一个数组直接在第二个数组之前。即：
源码解读：Collections.sort 排序原理
入口
list.sort(Test::compare);
进入list sort
public void sort(Comparator
