jdk8 Collections#sort究竟做了什么
前言
Collections#sort 追踪代码进去看，会调用到Arrays.sort，看到这里时，你肯定会想，这不是很简单，Arrays.sort在元素较少时使用插入排序，较多时使用快速排序，再多时使用快速排序，不过我要告诉你，这句话有一个前提，那就是针对基本类型排序时，是按照这个顺序，而 Collections#sort排的是list，不是这样的。
原理
jdk8 Arrays.sort在排序对象时是在较少元素时使用二分法插入排序，当元素较多时，会将元素分为多个块然后使用二分法插入排序也称二分排序，然后合并相邻的块，分而治之的思想。二分法插入排序简单来说就是对插入排序的优化，插入排序中，排序第k个元素时，会依次和已经排好序的元素比较，二分法插入排序时是通过二分查找的方式确定要插入的位置，这样就将时间复杂度降低了。
需要记住的点
1.Arrays.sort 在排序基本类型时使用了插入排序，快排和归并排序，快排是不稳定的排序，不过对于基本类型是否是稳定排序无须关心。
2.Arrays.sort 在排序对象时，使用的二分排序，这是一种稳定的排序，时间复杂度O(nlogn)。
写这篇博客的原因
在之前的认知过程中一直认为 Collections#sort 是插入排序，快排和归并排序，直到这周排查线上问题时才了解到之前的认知是错误的，所以决定仔细阅读一下文档和源码。
版权声明：本文为zhandouBlog原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。