寫這張之前我們需要先了解一下TIMSORT
TimSort演算法是一種起源於歸併排序和插入排序的混合排序演算法，設計初衷是為了在真實世界中的各種資料中可以有較好的效能。該演算法最初是由Tim Peters於2002年在Python語言中提出的。
TimSort 是一個歸併排序做了大量最佳化的版本。對歸併排序排在已經反向排好序的輸入時表現O(n2)的特點做了特別最佳化。對已經正向排好序的輸入減少回溯。對兩種情況混合（一會升序，一會降序）的輸入處理比較好。
上一篇文章我們講解了 arrays.sort 裡面的legacyMergeSort 這一篇我們講解最重要的一個演算法ComparableTimSort.sort
static void sort(Object[] a, int lo, int hi, Object[] work, int workBase, int workLen) { assert a != null && lo >= 0 && lo <= hi && hi <= a.length; int nRemaining = hi - lo; if (nRemaining < 2) return; // 當陣列的大小是 0 或 1 時 陣列總是有序的所以直接返回即可 // 這裡 MIN_MERGE=32 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. */ // 開始真正的tim sort 過程 ComparableTimSort ts = new ComparableTimSort(a, work, workBase, workLen); 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; }a) 從陣列開始處找到一組連線升序或嚴格降序（找到後翻轉）的數 b) Binary Sort：使用二分查詢的方法將後續的數插入之前的已排序陣列，binarySort 對陣列 a[lo:hi] 進行排序，並且a[lo:start]是已經排好序的。演算法的思路是對a[start:hi] 中的元素，每次使用binarySearch 為它在 a[lo:start] 中找到相應位置，並插入。
開始真正的TimSort過程：
選取minRun大小，之後待排序陣列將被分成以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 位，再加上第六位。a) 如果陣列大小為2的N次冪，則返回16（MIN_MERGE / 2） b) 其他情況下，逐位向右位移（即除以2），直到找到介於16和32間的一個數
do-while
找到初始的一組升序數列，countRunAndMakeAscending 會找到一個run ，這個run 必須是已經排序的，並且函式會保證它為升序，也就是說，如果找到的是一個降序的，會對其進行翻轉。2 若這組區塊大小小於minRun，則將後續的數補足，利用binarySort 對 run 進行擴充套件，並且擴充套件後，run 仍然是有序的。
3 當前的 run 位於 a[lo:runLen] ，將其入棧ts.pushRun(lo, runLen);//為後續merge各區塊作準備：記錄當前已排序的各區塊的大小
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 將剩餘元素合併。
5 重複 1 ~ 4，直到將待排序陣列排序完 6 Final Merge：如果此時還有區塊未merge，則合併它們.