TimSort算法是一种起源于归并排序和插入排序的混合排序算法，设计初衷是为了在真实世界中的各种数据中能够有较好的性能。
该算法最初是由Tim Peters于2002年在Python语言中提出的。
TimSort 是一个归并排序做了大量优化的版本号。
对归并排序排在已经反向排好序的输入时表现O(n2)的特点做了特别优化。对已经正向排好序的输入降低回溯。对两种情况混合（一会升序。一会降序）的输入处理比較好。
在jdk1.7之后。Arrays类中的sort方法有一个分支推断，当LegacyMergeSort.userRequested为true的情况下，採用legacyMergeSort，否则採用ComparableTimSort。而且在legacyMergeSort的凝视上标明了该方法会在以后的jdk版本号中废弃，因此以后Arrays类中的sort方法将採用ComparableTimSort类中的sort方法。
public static void sort(Object[] a, int fromIndex, int toIndex) { if (LegacyMergeSort.userRequested) legacyMergeSort(a, fromIndex, toIndex); else ComparableTimSort.sort(a, fromIndex, toIndex);} 以下是ComparableTimSort的sort方法 static void sort(Object[] a) { sort(a, 0, a.length);}static void sort(Object[] a, int lo, int hi) { rangeCheck(a.length, lo, hi); int nRemaining = hi - lo; if (nRemaining < 2) return; // Arrays of size 0 and 1 are always sorted // If array is small, do a "mini-TimSort" with no merges if (nRemaining < MIN_MERGE) { int initRunLen = countRunAndMakeAscending(a, lo, hi); binarySort(a, lo, hi, lo + initRunLen); return; } /** * 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. */ ComparableTimSort ts = new ComparableTimSort(a); int minRun = minRunLength(nRemaining); do { // Identify next run int runLen = countRunAndMakeAscending(a, lo, hi); // If run is short, extend to min(minRun, nRemaining) if (runLen < minRun) { int force = nRemaining <= minRun ? nRemaining : minRun; binarySort(a, lo, lo + force, lo + runLen); runLen = force; } // Push run onto pending-run stack, and maybe merge ts.pushRun(lo, runLen); ts.mergeCollapse(); // Advance to find next run lo += runLen; nRemaining -= runLen; } while (nRemaining != 0); // Merge all remaining runs to complete sort assert lo == hi; ts.mergeForceCollapse(); assert ts.stackSize == 1;} （1）传入的待排序数组若小于阈值MIN_MERGE（Java实现中为32。Python实现中为64）。则调用 binarySort，这是一个不包括合并操作的 mini-TimSort。 a) 从数组開始处找到一组连接升序或严格降序（找到后翻转）的数 b) Binary Sort：使用二分查找的方法将兴许的数插入之前的已排序数组。
binarySort对数组a[lo:hi]进行排序，而且a[lo:start]是已经排好序的。算法的思路是对a[start:hi]中的元素。每次使用binarySearch为它在a[lo:start]中找到对应位置，并插入。
（2）開始真正的TimSort过程：
（2.1） 选取minRun大小，之后待排序数组将被分成以minRun大小为区块的一块块子数组
a) 假设数组大小为2的N次幂，则返回16（MIN_MERGE / 2） b) 其它情况下，逐位向右位移（即除以2），直到找到介于16和32间的一个数
- minRun
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); n >>= 1; } return n + r; } 这个函数依据 n 计算出相应的 natural run 的最小长度。 MIN_MERGE 默觉得32，假设n小于此值，那么返回n 本身。否则会将 n 不断地右移。直到少于 MIN_MERGE，同一时候记录一个 r 值，r 代表最后一次移位n时。n最低位是0还是1。 最后返回 n + r，这也意味着仅仅保留最高的 5 位。再加上第六位。
（2.2）do-while
（2.2.1）找到初始的一组升序数列，countRunAndMakeAscending 会找到一个run 。这个run 必须是已经排序的。而且函数会保证它为升序，也就是说，假设找到的是一个降序的。会对其进行翻转。
（2.2.2）若这组区块大小小于minRun，则将兴许的数补足，利用binarySort 对 run 进行扩展。而且扩展后，run 仍然是有序的。
（2.2.3）当前的 run 位于 a[lo:runLen] ，将其入栈ts.pushRun(lo, runLen);//为兴许merge各区块作准备：记录当前已排序的各区块的大小
（2.2.4）对当前的各区块进行merge，merge会满足下面原则（如果X，Y，Z为相邻的三个区块）：
a) 仅仅对相邻的区块merge b) 若当前区块数仅为2，If X<=Y。将X和Y merge b) 若当前区块数>=3，If X<=Y+Z。将X和Y merge。直到同一时候满足X>Y+Z和Y>Z
因为要合并的两个
run是已经排序的，所以合并的时候，有会特别的技巧。如果两个run是run1,run2，先用gallopRight在run1里使用binarySearch查找run2 首元素的位置k, 那么run1中k前面的元素就是合并后最小的那些元素。然后，在run2中查找run1 尾元素的位置len2，那么run2中len2后面的那些元素就是合并后最大的那些元素。最后，依据len1与len2大小。调用mergeLo或者mergeHi将剩余元素合并。
（2.2.5） 反复2.2.1 ~ 2.2.4，直到将待排序数组排序完 （2.2.6） Final Merge：假设此时还有区块未merge，则合并它们
（3）演示样例
*注意*：为了演示方便，我将TimSort中的minRun直接设置为2，否则我不能用非常小的数组演示。。
。同一时候把MIN_MERGE也改成2（默觉得32），这样避免直接进入binary sort。
初始数组为[7,5,1,2,6,8,10,12,4,3,9,11,13,15,16,14] => 寻找连续的降序或升序序列 (2.2.1)。同一时候
countRunAndMakeAscending函数会保证它为升序 [1,5,7] [2,6,8,10,12,4,3,9,11,13,15,16,14]=> 入栈 (2.2.3) 当前的栈区块为[3]
=> 进入merge循环 (2.2.4) do not merge由于栈大小仅为1
=> 寻找连续的降序或升序序列 (2.2.1) [1,5,7] [2,6,8,10,12] [4,3,9,11,13,15,16,14]
=> 入栈 (2.2.3) 当前的栈区块为[3, 5]
=> 进入merge循环 (2.2.4) merge由于runLen[0]<=runLen[1] 1) gallopRight：寻找run1的第一个元素应当插入run0中哪个位置（”2”应当插入”1”之后），然后就能够忽略之前run0的元素（都比run1的第一个元素小） 2) gallopLeft：寻找run0的最后一个元素应当插入run1中哪个位置（”7”应当插入”8”之前），然后就能够忽略之后run1的元素（都比run0的最后一个元素大）这样须要排序的元素就仅剩下[5,7] [2,6]，然后进行mergeLow 完毕之后的结果： [1,2,5,6,7,8,10,12] [4,3,9,11,13,15,16,14]
=> 入栈 (2.2.3) 当前的栈区块为[8] 退出当前merge循环由于栈中的区块仅为1
=> 寻找连续的降序或升序序列 (2.2.1) [1,2,5,6,7,8,10,12] [3,4] [9,11,13,15,16,14] => 入栈 (2.2.3) 当前的栈区块大小为[8,2]
=> 进入merge循环 (2.2.4) do not merge由于runLen[0]>runLen[1]
=> 寻找连续的降序或升序序列 (2.2.1) [1,2,5,6,7,8,10,12] [3,4] [9,11,13,15,16] [14]
=> 入栈 (2.2.3) 当前的栈区块为[8,2,5]
=> do not merege run1与run2由于不满足runLen[0]<=runLen[1]+runLen[2] merge run2与run3由于runLen[1]<=runLen[2] 1) gallopRight：发现run1和run2就已经排好序 完毕之后的结果： [1,2,5,6,7,8,10,12] [3,4,9,11,13,15,16] [14]
=> 入栈 (2.2.3) 当前入栈的区块大小为[8,7] 退出merge循环由于runLen[0]>runLen[1]
=> 寻找连续的降序或升序序列 (2.2.1) 最后仅仅剩下[14]这个元素：[1,2,5,6,7,8,10,12] [3,4,9,11,13,15,16] [14]
=> 入栈 (2.2.3) 当前入栈的区块大小为[8,7,1]
=> 进入merge循环 (2.2.4) merge由于runLen[0]<=runLen[1]+runLen[2] 由于runLen[0]>runLen[2]，所以将run1和run2先合并。（否则将run0和run1先合并） 1) gallopRight & 2) gallopLeft 这样须要排序的元素剩下[13,15] [14]，然后进行mergeHigh 完毕之后的结果： [1,2,5,6,7,8,10,12] [3,4,9,11,13,14,15,16] 当前入栈的区块为[8,8]
=> 继续merge由于runLen[0]<=runLen[1] 1) gallopRight & 2) gallopLeft 须要排序的元素剩下[5,6,7,8,10,12] [3,4,9,11]。然后进行mergeHigh 完毕之后的结果： [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16] 当前入栈的区块大小为[16]
=> 不须要final merge由于当前栈大小为1
=> 结束
參考：
http://www.lifebackup.cn/timsort-java7.html
http://blog.csdn.net/on_1y/article/details/30109975
http://en.wikipedia.org/wiki/Timsort