當參數類型為對象數組時，在原來的版本使用的歸并排序（以后將會刪除 ），現在使用的timSort。
public static void sort(Object[] a) { if (LegacyMergeSort.userRequested) legacyMergeSort(a); else ComparableTimSort.sort(a); } //以后會拋棄 /** To be removed in a future release. */ PRivate static void legacyMergeSort(Object[] a) { Object[] aux = a.clone(); mergeSort(aux, a, 0, a.length, 0); }所以排序主要用了 ComparableTimSort.sort(Object[] a)。分為下面幾個主要步驟：
數組大于32時， 先算出一個合適的大小，在將輸入按其升序和降序特點進行了分區。排序的輸入的單位不是一個個單獨的數字，而是一個個的塊-分區。其中每一個分區叫一個run。針對這些 run 序列，每次拿一個run出來按規則進行合并。每次合并會將兩個run合并成一個 run。合并的結果保存到棧中。合并直到消耗掉所有的run，這時將棧上剩余的 run合并到只剩一個 run 為止。這時這個僅剩的 run 便是排好序的結果。
static void sort(Object[] a, int lo, int hi) { //小于32 ...... //大于32的情況 ComparableTimSort ts = new ComparableTimSort(a); //計算出run的長度 int minRun = minRunLength(nRemaining); do { //找出連續升序的最大個數 int runLen = countRunAndMakeAscending(a, lo, hi); // 如果run長度小于規定的minRun長度，先進行二分插入排序 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(); lo += runLen; nRemaining -= runLen; } while (nRemaining != 0); // 歸并所有的run ts.mergeForceCollapse(); }1.計算出run的最小的長度minRun
a) 如果數組大小為2的N次冪，則返回16（MIN_MERGE / 2）
b) 其他情況下，逐位向右位移（即除以2），直到找到介于16和32間的一個數
private static int minRunLength(int n) { int r = 0; // Becomes 1 if any 1 bits are shifted off while (n >= MIN_MERGE) { r |= (n & 1); n >>= 1; } return n + r; }2.求最小遞增的長度，如果長度小于minRun，使用插入排序補充到minRun的個數，操作和小于32的個數是一樣。 3.用stack記錄每個run的長度，當下面的條件其中一個成立時歸并，直到數量不變 runLen[i - 3] > runLen[i - 2] + runLen[i - 1] runLen[i - 2] > runLen[i - 1]
private void mergeCollapse() { while (stackSize > 1) { int n = stackSize - 2; if (n > 0 && runLen[n-1] <= runLen[n] + runLen[n+1]) { if (runLen[n - 1] < runLen[n + 1]) n--; //具體的歸并操作 mergeAt(n); } else if (runLen[n] <= runLen[n + 1]) { mergeAt(n); } else { break; // Invariant is established } } }關于歸并方法和對一般的歸并排序做出了簡單的優化。假設兩個 run 是 run1,run2 ，先用 gallopRight在 run1 里使用 binarySearch 查找run2 首元素 的位置k, 那么 run1 中 k 前面的元素就是合并后最小的那些元素。然后，在run2 中查找run1 尾元素 的位置 len2 ，那么run2 中 len2 后面的那些元素就是合并后最大的那些元素。最后，根據len1 與len2 大小，調用mergeLo 或者 mergeHi 將剩余元素合并。
private void mergeAt(int i) { int base1 = runBase[i]; int len1 = runLen[i]; int base2 = runBase[i + 1]; int len2 = runLen[i + 1]; runLen[i] = len1 + len2; if (i == stackSize - 3) { runBase[i + 1] = runBase[i + 2]; runLen[i + 1] = runLen[i + 2]; } stackSize--; int k = gallopRight((Comparable<Object>) a[base2], a, base1, len1, 0); assert k >= 0; base1 += k; len1 -= k; if (len1 == 0) return; len2 = gallopLeft((Comparable<Object>) a[base1 + len1 - 1], a, base2, len2, len2 - 1); assert len2 >= 0; if (len2 == 0) return; if (len1 <= len2) mergeLo(base1, len1, base2, len2); else mergeHi(base1, len1, base2, len2); }4.最后歸并還有沒有歸并的run，知道run的數量為1
為了演示方便，我將TimSort中的minRun直接設置為2，否則我不能用很小的數組演示。。。同時把MIN_MERGE也改成2（默認為32），這樣避免直接進入二分插入排序。
初始數組為[7,5,1,2,6,8,10,12,4,3,9,11,13,15,16,14]
尋找第一個連續的降序或升序序列：[1,5,7] [2,6,8,10,12,4,3,9,11,13,15,16,14]
stackSize=1，所以不合并，繼續找第二個run
找到一個遞減序列，調整次序：[1,5,7] [2,6,8,10,12] [4,3,9,11,13,15,16,14]
因為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]
尋找連續的降序或升序序列[1,2,5,6,7,8,10,12] [3,4] [9,11,13,15,16,14]
不進行歸并排序，因為runLen[0]>runLen[1]
尋找連續的降序或升序序列：[1,2,5,6,7,8,10,12] [3,4] [9,11,13,15,16] [14]
因為runLen[1]<=runLen[2]，所以需要歸并
使用gallopRight，發現為正常順序。得[1,2,5,6,7,8,10,12] [3,4,9,11,13,15,16] [14]
最后只剩下[14]這個元素：[1,2,5,6,7,8,10,12] [3,4,9,11,13,15,16] [14]
因為runLen[0]<=runLen[1]+runLen[2]所以合并。因為runLen[0]>runLen[2]，所以將run1和run2先合并。（否則將run0和run1先合并） 完成之后的結果： [1,2,5,6,7,8,10,12] [3,4,9,11,13,14,15,16]
完成之后的結果：[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]
參考：http://blog.csdn.net/bruce_6/article/details/38299199
新聞熱點
疑難解答
