算法介绍
JDK1.8中，对于列表的排序，java.util.List中提供了sort方法，调用的Arrays.sort(T[],Comparator<? super T>)，Arrays提供的对Object的一种排序方法（这里用的是泛型T，还有Object[]对应的排序方法），在该方法中可以看到使用的是TimSort类的静态方法对数组进行排序，TimSort类的内容就是TimSort算法的实现。
TimSort是一种混合排序算法，内部使用了插入排序（二分插入排序）和归并排序，是在数组中的数据都是部分有序（正序或倒序）的情况下，将两种排序算法进行结合优化带来排序效率的提高。
对于插入排序，其时间复杂度为O(n^2)，但在数据基本有序的情况下有教好的排序性能，而二分插入排序是对插入排序的优化，减少比较次数，但没有减少移动次数，时间复杂度为O(n*logn)。
对于归并排序，其时间复杂度为O(n * logn)，排序性能比较高，但其缺点是当数组长度比较小时，归并的效率并不高且浪费空间；另一方面是如果两个序列的长度相差较大，一个长序列和一个序列进行归并，其归并带来的排序效率无法很好的体现。
算法步骤
步骤
TimSort排序算法的步骤如下：
如果数组的长度小于MIN_MERGE=32时，直接使用二分插入排序。
将待排序的数组划分成一个个子数组run，数组长度最小阈值为minRun，minRun的值根据数组长度进行计算。
从数组第一位开始获取连续有序的run，为倒序时将数组翻转为正序。如果此时run的长度小于minRun，则使用二分插入算法从下一位进行补充。
-
将上一步得到的run推入栈中，保存当次run的起始下标位置baseLen[]和run的长度runLen[]。判断栈中的run是否需要合并。当前栈中run数量大于1时进行循环
- n = stackSize - 2
- n = 0(run数量为2)，runLen[n] <= runLen[n+1]时，将n与n+1的run进行合并（归并排序）
- n > 0 且 runLen[n-1] <= runLen[n] + runLen[n+1]时，如果runLen[n - 1] < runLen[n + 1]，n-1 与 n 合并，否则 n 与 n+1 合并
移动起始下标，重复上述两步遍历到数组尾部。
将栈中剩余的run进行最终合并，归并为一个正序的有序数组。
其中有几个关键点
MIN_MERGE
将要合并序列的大小的最小值。上面提到归并排序的缺点，当数组长度比较小时，归并的效率不高且浪费空间，所以直接采用二分插入排序。
minRun
划分的run对应的数组的最小阈值，其计算逻辑为
- 当数组长度小于MIN_MERGE，直接返回数组长度，相当不做归并排序只进行插入排序，与上述对MIN_MERGE判断一致。
- 如果数组长度是2的精准乘方（2^m，2的阶乘），返回MIN_MERGE/2
- 其余返回整数k，MIN_MERGE/2 <= K <= MIN_MERGE，n/k接近但严格小于2的精准乘方。（严格小于即差值为1）
private static int minRunLength(int n) {
assert n >= 0;
int r = 0; // Becomes 1 if any 1 bits are shifted off
while (n >= MIN_MERGE) {
r |= (n & 1); // 奇数二进制低位为1，&1=1;偶数二进制低位为0，&1=0
n >>= 1; // 向右移一位，相当于除以2
}
return n + r;
}
上述代码为minRun的计算源码，计算逻辑为：当n>=32时，n除以2；当n不为2的阶乘时，r=1，否则r=0（n/2的过程中出现奇数）,返回n+r。
由于TimSort在数组长度小于MIN_MERGE=32时直接使用二分插入排序，因为minRun的最小值为MIN_MERGE/2=16。
栈
TimSort中并没有初始化一个堆栈，而是使用两个数据记录每个run的信息，run的起始下标位置信息baseLen[]、run的长度信息runLen[]。runBase[i] +runLen[i] = runBase[i+1]
在run合并的过程中是从后往前的进行合并的，合并后会将baseLen及runLen中的信息进行更新。
图示
TimSort算法的图示如下(为方便演示，假设minRun=4)
run合并
每当一个run入栈的时候，都会判断栈中的run是否需要进行合并。每次循环都以倒数第二个run做基准进行判断，判断逻辑在步骤中已整理。当判断需要合并时，就会进行一次归并排序，相比普通归并排序从下标0位开始，此时run对应的数组已经是有序的，对归并过程是友好的。
对run归并的处理逻辑在JDK1.8的java.util.TimSort.mergeAt（）方法。简化的流程如下：
- 找出run2的第一个元素在run1的位置（偏移个数），如比run1的第一个元素小则为0，获取run1对比起始下标
- 找出run1的最后一个元素在run2的位置，获取run2移动对比长度
- 从run1对比起始下标（dest）开始，将run1剩余元素拷贝到数组tmp中（下标cursor1）
- 从run2起始下标（cursor2）开始循环与tmp[cursor1]对比，如a[cursor2]<tmp[cursor1]，则a[dest]=a[cursor2]，cursor2加1，dest加1；如a[cursor2]>=tmp[cursor1]，则a[dest]=tmp[cursor1]，cursor1加1，dest加1
- 循环结束，如tmp中存在未遍历元素，将剩余元素从数组dest位置拷贝覆盖。
下图为上述TimSort算法演示图中第一次run合并的过程。
上图run2的第一个元素比run1的第一个元素小，则run1全部被拷贝进tmp，若将run1第一个元素修改为2（比4小），则如下图，run1的第一个元素2及run2的最后一个元素18是不需要比较移动的。这种处理方式能减少比较和移动次数，提高归并排序的性能，也是归并排序在待归并序列有序情况下的优势。
复杂度及稳定性
TimSort算法主流程的源码如下：
static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> c,
T[] work, int workBase, int workLen) {
assert c != null && a != null && lo >= 0 && lo <= hi && hi <= a.length;
int nRemaining = hi - lo;
if (nRemaining < 2)
return; // Arrays of size 0 and 1 are always sorted
// 数组长度小于MIN_MERGER，不进行归并处理
if (nRemaining < MIN_MERGE) {
// 从lo位置开始找出有序的序列，如果是倒序装换为正序
int initRunLen = countRunAndMakeAscending(a, lo, hi, c);
// 二分插入排序，lo+iniRunLen为起始位置（因为这之前的都是有序且正序的）
binarySort(a, lo, hi, lo + initRunLen, c);
return;
}
/**
*实例化TimSort对象
* March over the array once, left to right, finding natural runs,
* extending short natural runs to minRun elements, and merging runs
* to maintain stack invariant.
*/
TimSort<T> ts = new TimSort<>(a, c, work, workBase, workLen);
// run最小长度
int minRun = minRunLength(nRemaining);
do {
// Identify next run
int runLen = countRunAndMakeAscending(a, lo, hi, c);
// run长度小于minRun，使用插入法进行补充
if (runLen < minRun) {
int force = nRemaining <= minRun ? nRemaining : minRun;
binarySort(a, lo, lo + force, lo + runLen, c);
runLen = force;
}
// 将run推入栈中，并判断是否需要合并
ts.pushRun(lo, runLen);
ts.mergeCollapse();
// Advance to find next run
lo += runLen;
nRemaining -= runLen;
} while (nRemaining != 0);
// 循环结束，将栈中剩余的序列合并
assert lo == hi;
ts.mergeForceCollapse();
assert ts.stackSize == 1;
}
从源码中可以看出，当待排序数组长度小于MIN_MERGER且已经是有序时，只进行一次查找有序序列的过程（countRunAndMakeAscending），是对数组的一次遍历，此时不需要进行二分插入排序也不需要进行归并。即最好情况下TimSort的时间复杂度为O(n)。
平均来看，使用了二分插入排序和归并排序，TimSort的时间复杂度为O(n*logn)。
在归并的过程使用了临时数组tmp存放待比对移动的元素，其空间复杂度为O(n)。
在二分插入即归并的过程中，对于大小相同的元素，没有改变其先后顺序，因此TimSort是一种稳定的排序算法。
快速排序的平均时间复杂度也为O(n*logn)，但快速排序是一种不稳定的排序，无法保证排序前后相同大小元素的有序性，这在某些场景下会出现影响。
TimSort与ComparableTimSort
java.util包下还有一个类似的类ComparableTimSort，是对实现了Comparable接口的对象的TimSort排序应用，而不是显式地传进去一个Comparator对象，流程一致。
