之前一直沒關注過Java底層排序的演算法，才仔細看了下Timsort。

Timsort 是一個混合、穩定的排序演算法，簡單來說就是

歸併排序

和

二分插入排序

演算法的混合體，號稱世界上最好的排序演算法。

它由 Tim Peters 在 2002 年實現，一直是 Python 的標準排序演算法。Java 在 1。7 後增加了 Timsort API ，從Java中的

Arrays。sort

可以看出它是預設的排序演算法，主要用於

非原始型別陣列排序。

所以不管是進階程式設計還是面試，理解 Timsort 都是比較重要。

// List sort（） default void sort（Comparator<？ super E> c） { Object［］ a = this。toArray（）； //陣列排序 Arrays。sort（a， （Comparator） c）； 。。。 }// Arrays。sort public static void sort（T［］ a， Comparator<？ super T> c） { if （c == null） { sort（a）； } else { // 廢棄版本 if （LegacyMergeSort。userRequested） legacyMergeSort（a， c）； else TimSort。sort（a， 0， a。length， c， null， 0， 0）； } } public static void sort（Object［］ a） { if （LegacyMergeSort。userRequested） legacyMergeSort（a）； else ComparableTimSort。sort（a， 0， a。length， null， 0， 0）； }

理解 Timsort 需要先回顧下以下知識。

指數搜尋

指數搜尋，也被稱為加倍搜尋，是一種用於在大型陣列中搜索元素而建立的演算法。它是一個兩步走的過程。首先，該演算法試圖找到目標元素存在的範圍

（L，R）

，然後在這個範圍內使用二叉搜尋來尋找目標的準確位置。該搜尋演算法在大量有序陣列中比較有效。

二分插入排序

插入排序演算法很簡單，大體過程是從第二個元素開始，依次向前移動交換元素直到找到合適的位置。

插入排序最優時間複雜度也需要 O（n） ，我們可以使用二分查詢來減少插入時元素的比較次數，將時間複雜度降為 O（log n）。但是注意，二分查詢插入排序仍然需要移動相同數量的元素，但是複製陣列的時間消耗低於逐一互換操作。

特點：

二分插入排序主要優點是在小資料集場景下排序效率很高。

public static int［］ sort（int［］ arr） throws Exception { // 開始遍歷第一個元素後的所有元素 for （int i = 1； i < arr。length； i++） { // 需要插入的元素 int tmp = arr［i］； // 從已排序最後一個元素開始，如果當前元素比插入元素大，就往後移動 int j = i； while （j > 0 && tmp < arr［j - 1］） { arr［j］ = arr［j - 1］； j——； } // 將元素插入 if （j ！= i） { arr［j］ = tmp； } } return arr； } public static int［］ binarySort（int［］ arr） throws Exception { for （int i = 1； i < arr。length； i++） { // 需要插入的元素 int tmp = arr［i］； // 透過二分查詢直接找到插入位置 int j = Math。abs（Arrays。binarySearch（arr， 0， i， tmp） + 1）； // 找到插入位置後，透過陣列複製向後移動，騰出元素位置 System。arraycopy（arr， j， arr， j + 1， i - j）； // 將元素插入 arr［j］ = tmp； } return arr； }

歸併排序

歸併排序是分而治之策略的演算法，包含兩個主要的操作：

分割

與

合併

。大體過程是，透過遞迴將陣列不斷分成兩半，一直到無法再分割（也就是陣列為空或只剩一個元素），然後進行合併排序。簡單來說合並操作就是不斷取兩個較小的排序陣列然後將它們組合成一個更大的陣列。

特點：

歸併排序主要為大資料集場景設計的排序演算法。

public static void mergeSortRecursive（int［］ arr， int［］ result， int start， int end） { // 跳出遞迴 if （start >= end） { return； } // 待分割的陣列長度 int len = end - start； int mid = （len >> 1） + start； int left = start； // 左子陣列開始索引 int right = mid + 1； // 右子陣列開始索引 // 遞迴切割左子陣列，直到只有一個元素 mergeSortRecursive（arr， result， left， mid）； // 遞迴切割右子陣列，直到只有一個元素 mergeSortRecursive（arr， result， right， end）； int k = start； while （left <= mid && right <= end） { result［k++］ = arr［left］ < arr［right］ ？ arr［left++］ ： arr［right++］； } while （left <= mid） { result［k++］ = arr［left++］； } while （right <= end） { result［k++］ = arr［right++］； } for （k = start； k <= end； k++） { arr［k］ = result［k］； } } public static int［］ merge_sort（int［］ arr） { int len = arr。length； int［］ result = new int［len］； mergeSortRecursive（arr， result， 0， len - 1）； return arr； }

Timsort 執行過程

演算法大體過程是，如果陣列長度小於指定閥值（

MIN_MERGE

）直接使用二分插入演算法完成排序，否則執行下面步驟：

先從陣列左邊開始，執行

升序執行

得到一個

子序列

。

將這個

子序列

放入執行堆疊裡，等待

執行合併

。

檢查執行堆疊裡的

子序列

，如果滿足

合併條件

則執行合併。

重複第一個步驟，執行下一個

升序執行

。

升序執行

升序執行

就是從陣列查詢一段連續遞增（升序）或遞減（降序）子序列的過程，如果子序列為降序則將它反轉為升序，也可以將這個過程簡稱為

run

。比如陣列 ［2，3，6，4，9，30］，可以查詢到三個子序列，［2，3，6］、［4，9］、［30］，或說3個

run

。

幾個關鍵閥值

MIN_MERGE

這是個常數值，可以簡單理解為執行歸併的最小閥值，如果整個陣列長度小於它，就沒必要執行那麼複雜的排序，直接二分插入就行了。在 Tim Peter 的 C 實現中為 64，但實際經驗中設定為 32 效果更好，所以 java 裡面的值為 32。

降序反轉時為保證穩定性，相同元素不會被顛倒。

minrun

在合併序列的時候，如果

run

數量等於或者略小於 2 的冪次方的時候，合併效率最高；如果略大於 2 的冪次方，效率就會顯著降低。所以為了提高合併效率，需要儘量控制每個

run

的長度，透過定義一個

minrun

來表示每個

run

的最小長度，如果長度太短，就用二分插入排序把

run

後面的元素插入到前面的

run

裡面。

一般在執行排序演算法之前，會先計算出這個 minrun（它是根據資料的特點來進行自我調整），minrun 會從32到64選擇一個數字，因此資料的大小除以 minrun 等於或略小於 2 的冪次方。比如長度是 65 ，那麼 minrun 的值就是 33；如果長度是 165，minrun 就是 42。

看下 Java 裡面的實現，如果

資料長度

（n） < MIN_MERGE，則返回資料長度。如果

資料長度

恰好是 2 的冪次方，則返回MIN_MERGE/2

也就是16，否則返回一個MIN_MERGE/2 <= k <= MIN_MERGE範圍的值k，這樣可以使的 n/k 接近但嚴格小於 2 的冪次方。

private static int minRunLength（int n） { assert n >= 0； int r = 0； // 如果低位任何一位是1，就會變成1 while （n >= MIN_MERGE） { r |= （n & 1）； n >>= 1； } return n + r； }

MIN_GALLOP

MIN_GALLOP 是為了優化合並的過程設定的一個閾值，控制進入

GALLOP

模式中，

GALLOP

模式放在後面講。

下面是 Timsort 執行流程圖

執行合併

當棧裡面的

run

滿足合併條件時，它就將棧裡面相鄰的兩個run 進行合併。

合併條件

Timsort 為了執行平衡合併（讓合併的 run 大小盡可能相同），制定了一個合併規則，對於在棧頂的三個run，分別用X、Y 和 Z 表示他們的長度，其中 X 在棧頂，它們必須始終維持以下下的兩個規則：

Z > Y + X Y > X

一旦有其中的一個條件不被滿足，則將 Y 與 X 或 Z 中的較小者合併生成新的

run

，並再次檢查棧頂是否仍然滿足條件。如果不滿足則會繼續進行合併，直至棧頂的三個元素都滿足這兩個條件，如果只剩兩個

run

，則滿足 Y > X 即可。

如下下圖例子

當 Z <= Y+X ，將 X+Y 合併，此時只剩下兩個run。

檢測 Y < X ，執行合併，此時只剩下 X，則退出合併檢測。

我們看下 Java 裡面的合併實現

private void mergeCollapse（） { // 當存在兩個以上run執行合併檢查 while （stackSize > 1） { // 表示 Y int n = stackSize - 2； // Z <= Y + X if （n > 0 && runLen［n-1］ <= runLen［n］ + runLen［n+1］） { // 如果 Z < X 合併Z+Y ，否則合併X+Y if （runLen［n - 1］ < runLen［n + 1］） n——； // 合併相鄰的兩個run，也就是runLen［n］ 和 runLen［n+1］ mergeAt（n）； } else if （runLen［n］ <= runLen［n + 1］） { // Y <= X 合併 Y+X mergeAt（n）； } else { // 滿足兩個條件，跳出迴圈 break； } } }

合併記憶體開銷

原始歸併排序空間複雜度是 O（n） 也就是資料大小。為了實現中間項，Timsort 進行了一次歸併排序，時間開銷和空間開銷都比 O（n） 小。

最佳化是為了儘可能減少資料移動，佔用更少的臨時記憶體，先找出需要移動的元素，然後將較小序列複製到臨時記憶體，再按最終順序排序並填充到組合序列中。

比如我們需要合併 X ［1， 2， 3， 6， 10］ 和 Y ［4， 5， 7， 9， 12， 14， 17］，X 中最大元素是10，我們可以透過二分查詢確定，它需要插入到 Y 的第 5個位置才能保證順序，而 Y 中最小元素是4，它需要插入到 X 中的第4個位置才能保證順序，那麼就知道了［1， 2， 3］ 和 ［12， 14， 17］ 不需要移動，我們只需要移動 ［6， 10］ 和 ［4， 5， 7， 9］，然後只需要分配一個大小為 2 臨時儲存就可以了。

合併最佳化

在歸併排序演算法中合併兩個陣列需要一一比較每個元素，為了優化合並的過程，設定了一個閾值 MIN_GALLOP，當B中元素向A合併時，如果A中連續 MIN_GALLOP 個元素比B中某一個元素要小，那麼就進入GALLOP模式。

根據基準測試，比如當A中連續7個以上元素比B中某一元素小時切入該模式效果才好，所以初始值為7。

當進入GALLOP模式後，搜尋演算法變為指數搜尋，分為兩個步驟，比如想確定 A 中元素x在 B 中確定的位置

首先在 B 中找到合適的索引區間 使得 x 元素在這個範圍內；

然後在第一步找到的範圍內透過二分搜尋來找到對應的位置。

只有當一次執行的初始元素不是另一次執行的前七個元素之一時，馳騁才是有益的。這意味著初始閾值為 7。