這麽多年排序白學了，原來每次排序都在使用世界上最快的排序演算法 TimSort

在電腦科學的領域，排序演算法是每位學生必學的基礎，而排序的需求是每位程式設計師在編程過程中都會遇到的。

在你輕松呼叫 .sort() 方法對數據進行排序時，是否曾好奇過，這個簡單的方法背後使用的是哪種排序演算法呢？

本文將帶你走進 TimSort，一個在標準函式庫中廣泛使用的排序演算法。

這個演算法由工程師 Tim Peters 於 2001 年專為 Python 設計，並自 Python 2.3 版本起成為其預設排序演算法。它的影響不止於此，Java、Android、GNU Octave、Chrome 的 V8 引擎、Swift 以及 Rust 等也紛紛采用了這一演算法。

那麽，是什麽讓 TimSort 在眾多排序演算法中獨樹一幟，贏得了如此廣泛的套用和認可呢？

在本文中，我們將深入剖析 TimSort 的內部機制，揭示其背後的高效實作原理，讓你領略這一演算法的獨特魅力。

🧩小規模數據的高效處理：插入排序

TimSort 是一個結合了插入排序和歸並排序的混合排序演算法，特別適合處理真實世界的各種數據。

從這句定義中您可能會好奇，為什麽 TimSort 選擇了插入排序和歸並排序？為什麽說它適合處理真實世界的數據？

讓我們首先探討第一個問題，為什麽插入排序成為了 TimSort 的關鍵組成部份。

盡管插入排序的理論時間復雜度為 O(n^2) ，看似不及 O(nlogn) 的高效排序演算法，但插入排序的實際效率卻非常高效，尤其是在處理小規模數據集時。

這是因為插入排序只涉及兩個簡單操作： 比較 和 移動 。

透過比較，我們能夠確定新元素的插入點；透過移動，我們為新元素的插入騰出空間。

關鍵在於， 對於小數據集而言， n^2 與 nlogn 的差異並不顯著，復雜度不占主導作用，此時每輪單元的運算元量才起到決定性因素。 得益於其簡潔的操作，插入排序在小規模數據集上的表現通常非常出色。

但究竟什麽規模的數據集算是「小」呢？

以 Python 為例，當數據集大小小於 64 時，它會預設采用插入排序。而在 Java 中，這一界限則被設定在了 32。

➗插入排序的最佳化：二分插入排序

對於 TimSort 演算法來說，傳統插入排序也存在進一步提升效能的空間。

回顧一下，插入排序涉及的關鍵操作有兩個：比較和移動。這其中，對於一個陣列來說，移動的總次數是固定不變的，因此，我們可以嘗試從減少比較的次數來最佳化。

在插入排序的執行過程中，數據被劃分為已排序和未排序的兩個部份。在已排序部份，我們尋找未排序部份下一個元素的插入位置時，常規做法是采用線性尋找。

但 TimSort 采用了更高效的策略——二分尋找法。利用二分尋找在已排序部份尋找插入點，大幅減少了比較次數。

對小規模數據集而言，這種最佳化尤其有效，能顯著提升排序的效率。

舉個例子，如上面視訊所示，在使用傳統插入排序時，為將元素 2 插入正確位置，需要進行 5 次比較。而在二分插入排序中，這一過程可以縮減至僅需 2 次比較，從而顯著提高排序效率。

🌟TimSort 的工作原理

在詳細了解了插入排序在 TimSort 中的作用之後，接下來我們可以進一步了解歸並排序在 TimSort 中的套用。不過在這之前，我們需要知道 TimSort 的整體工作原理。

TimSort 的設計目標是最大限度地利用在絕大多數實際數據中已經存在的連續有序序列，這些被稱為自然序列 natural run。

在演算法的執行過程中，它遍歷數據集，借助於這些自然序列，必要時將附近的元素添加進去，形成一個個的數據塊 run，其中每個 run 中的元素都會進行排序。

隨後，這些有序的 run 被堆疊在一個棧中，形成了演算法處理過程的一個關鍵結構。

當一個新的 run 被辨識並加入到棧中後，TimSort 會根據棧頂多個 run 的長度來判斷，是否應該合並棧頂附近的 run。

這個過程將持續進行，直到所有數據都遍歷完。

遍歷結束後，棧中剩余的所有 run 每次兩兩合並，直到最終形成一個完整有序的 run。

相比傳統歸並排序，合並預排序的 run 會大大減少了所需的比較次數，從而提升了整體的排序效率。

現在，你可能對 TimSort 演算法的細節產生了許多疑問。run 是如何形成的？這些 run 是如何利用數據中已存在的自然序列？當 run 被加入到棧中後，依據什麽規則來決定是否合並？……

不用擔心，接下來我們將逐一解答這些問題，帶你更深入地理解 TimSort 演算法。

🧮計算 minrun

在 TimSort 演算法中，run 的生成非常關鍵，而這一過程的核心是確定 run 最小長度 minrun。這個長度的設定是為了在排序過程中達到兩個關鍵目標：

實驗研究表明，當 minrun 小於 8 時，第一條原則難以滿足；而當 minrun 超過 256 時，第二條原則受到影響。

因此，最佳的 minrun 長度範圍被確定在 32 到 64 之間。

這個範圍與我們之前提到的插入排序中小規模數據集的長度範圍非常接近，這並非巧合。事實上，Timsort 在生成 run 時也會利用到插入排序。

具體計算 minrun 的方法如下：

1. 目標 ：選取一個 minrun 值，以使長度為 n 的陣列被分割成約 n/minrun 個 runs，每個 run 包含大約 32 到 64 個元素。

2. 計算方法 ：選擇最接近 n/(2^k) 的 minrun 值，這裏 k 是使 n/(2^k) 落在32至64之間的最大整數。然後設定 minrun 為 n/(2^k) 。

例如，對於長度為 65 的陣列，minrun 將設定為33，形成 2 個runs；對於長度為 165 的陣列，minrun 設定為42，形成 4 個runs。

這個計算過程涉及到 (2^k) ，可以透過位移操作高效實作：

defget_minrun(n):
# 用於記錄在不斷右移過程中，n的最低位上非零位的數量
r = 0
while n >= 64:
# 檢查n的最低位是否為1，若是，則設定r為1
r |= n & 1
# 向右移動一位，相當於n除以2
n >>= 1
# 返回n加上r，n是原始值的最高6位，r是表示過程中n是否有非零最低位的標誌
return n + r


這種方法不僅保證了 minrun 的有效性，而且利用了位運算的高效性，體現了 TimSort 設計的巧思。

🚀run 的生成過程

在掌握了 minrun 的計算方法之後，我們現在可以探究 run 是如何生成的。

TimSort 的核心目標是充分利用數據中已存在的連續有序序列來生成 run，但這是如何實作的呢？

TimSort 的處理流程可分為以下幾個關鍵步驟：

1. TimSort 開始掃描整個陣列，尋找連續的升序或降序序列。

2. 如果遇到升序部份，TimSort 會持續掃描直到升序結束。

3. 如果遇到降序部份，TimSort 會繼續掃描直到降序結束，並隨後將這部份翻轉成升序。

如果上述步驟辨識的 run 未達到 minrun 長度 ，TimSort 會繼續擴充套件這個 run，向陣列後方遍歷，納入更多元素，直至達 minrun 長度。在這個階段，新加入元素的順序並不重要。

一旦擴充套件完成，這個擴充套件後的 run（無論其最初是否有序）都將透過插入排序進行排序，以確保其內部有序。

如果辨識的 run 長度遠超 minrun ，對於這些較長的連續有序序列，TimSort 會保持其原始長度，不進行切割。這是因為較長的有序序列對於減少後續合並操作的復雜度非常有利。

對於這些超長的 run，通常無需進行額外排序，除非它們是降序，這時 TimSort 會先將其翻轉成升序。

透過這些策略，TimSort 能夠高效地生成一個有序的、長度至少為 minrun 的 run，為後續的歸並排序過程奠定了堅實基礎。

💾棧中 run 的合並規則

在 TimSort 演算法中，每生成一個新的 run，它就會被加入到一個專門的棧中。

這時，TimSort 會對棧頂的三個 run（我們稱它們為X、Y和Z）進行檢查，以確保它們符合特定的合並規則：

1. |Z| > |Y| + |X|

2. |Y| > |X|

如果這些條件沒有被滿足，Y 就會與 X 或 Z 中較小的一個合並，並重新檢查上述條件。當所有條件都滿足時，可以在數據中繼續遍歷生成新的 run。

這種獨特的合並規則是為了實作什麽目標呢？

在 TimSort 的合並規則下，最終保留在棧中的每個 run 的長度至少等於前兩個 run 的總長度（由於滿足 |Z| > |Y| + |X| 和 |Y| > |X| 的規則）。

這種設計意味著，隨著時間的推移，棧中 run 的長度會逐漸增大，其增長方式類似於費氏數列。

這種增長模式的一個重要優勢在於，它提供了一種有效的方式來平衡數據遍歷完成之後 run 的合並操作，同時避免了過於頻繁的合並。

在最理想情況下，這個棧從頂部到底部 run 的長度應該是[2,2,4,8,16,32,64,...]。這樣，從棧頂到棧底的合並過程中，每次合並的兩個 run 的長度都是相等的，形成了完美的合並。

透過這些巧妙的規則，TimSort 在保證合並操作近似均衡的同時，也確保了在追求均衡和簡化合並決策之間的權衡。

正如 Tim Peters 所指出的，找到一種方式來維持棧中這兩個規則，是一個極具智慧的折中選擇。

📚合並過程中的空間開銷

了解完 TimSort 的工作原理和 run 在棧中的合並規則之後，我們現在來看 TimSort 中的最後一個重要環節：如何高效地運用歸並排序？

雖然傳統的歸並排序也擁有 O(nlogn) 的時間復雜度，但它並不是原地排序，並且需要額外的 O(n) 空間開銷，這使得它並沒有被廣泛地運用。

當然，也有改良過的原地歸並排序的實作，但它們的時間開銷就會比較大。為了在效率和空間節約之間取得平衡，TimSort 采用了一種改進的歸並排序，其空間開銷遠小於 O(n) 。

以一個具體例子來說明：假設我們有兩個已排序的陣列 [1, 2, 3, 6, 10] 和 [4, 5, 7, 9, 12, 14, 17] ，目標是將它們合並。

在這個例子中，我們可以觀察到：

因此，兩個陣列中的 [1, 2, 3] 和 [12, 14, 17] 已經位於它們的最終位置，無需移動。我們實際上需要合並的部份是 [6, 10] 和 [4, 5, 7, 9] 。

在這種情況下，我們只需要建立一個大小為 2 的臨時陣列，將 [6, 10] 復制到其中，然後在原陣列中將它們與 [4, 5, 7, 9] 合並。

這個例子展示了從前往後的合並過程。同樣，還有從後往前合並的情況：

與傳統歸並排序相比，TimSort 在這裏采用的最佳化策略顯著減少了元素移動的次數，縮短了執行時間，並大幅降低了臨時空間的需求。

⚡合並過程中的 galloping mode

在歸並排序過程中，通常的做法是逐個比較兩個陣列中的元素，並將較小的元素依次放置到合適的位置。

然而，在某些情況下，這種方法可能涉及大量冗余的比較操作，尤其是當一個陣列中的元素連續地勝出另一個陣列時。

想象一下，如果我們有兩個極端不平衡的陣列：

A = [1, 2, 3, …, 9999, 10000]

B = [20000, 20001, …, 29999, 30000]

在這種情況下，為了確定 B 中元素的正確插入點，我們需要進行高達 10000 次的比較，這無疑是低效的。

如何解決這個問題呢？

TimSort 的解決方案是引入了所謂的「躍進模式」（galloping mode）。這種模式基於一個假設：如果一個陣列中的元素連續勝出另一個陣列中的元素，那麽這種趨勢可能會持續下去。

TimSort 會統計從一個陣列連續選中的元質數量，一旦連續勝出次數達到了稱為 min_gallop 的閾值時，TimSort 就會切換到躍進模式。

在這種模式下，演算法將不再逐個比較元素，而是將實施一種指數級搜尋（exponential search）。以指數級的步長（2^k）進行跳躍，首先檢查位置 1 的元素，然後是位置 3 (1 + 2^1 )，接著是位置 7 (3 + 2^2)，以此類推。

當首次找到大於或等於比較元素的位置時，我們就將搜尋範圍縮小到上一步的位置（2^(k-1) + 1）和當前步的位置（2^k + 1）之間的區間。

在這個區間內進行更二分搜尋，以快速定位正確的插入位置。

據開發者的基準測試，只有當一個陣列的首元素並不處於另一陣列的前 7 位置時，躍進模式才真正帶來優勢，因此 min_gallop 的閾值為 7。

上面的步驟看起來比較復雜，我們以兩個陣列為例：

A = [1, 25, 31, 37]

B = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36]

根據之前合並過程中的空間開銷原則，A 中的元素 1 是固定的，此時將 25, 31, 37 移動到臨時空間進行合並排序。

在這種情況下，當 25 在與 B 陣列元素比較時連續勝出，觸發了躍進模式。

演算法直接跳躍到位置 15 (7 + 2^3)，發現 30 大於 25 。

進而在位置 7 和 15 之間執行二分搜尋，以找到 25 的插入點。

雖然躍進模式在某些情況下能極大提高效率，但它並非總是最優選擇。有時，躍進模式可能導致更多的比較操作，尤其是在數據分布較為均勻時。

為了避免這種情況，TimSort采用了兩種策略：一是當辨識到躍進模式的效率不及二分搜尋時，會結束躍進模式；二是根據躍進模式的成功與否調整 min_gallop 值。

如果躍進模式成功且連續選擇的元素均來自同一陣列，min_gallop 值會減 1，以鼓勵再次使用躍進模式；反之，則加 1，減少再次使用躍進模式的可能性。

💡結語：TimSort - 數據排序的實用革新

在探索數據排序這個歷史悠久且充滿挑戰的領域中，TimSort 演算法不僅是一項技術成就，更是實用性與創新的傑出典範。它的出現，不單單是演算法領域的一個新節點，更是對現實世界復雜數據處理需求的有效回應。

TimSort 的真正魅力不僅在於它的高效率，更在於它對實際數據特性的深入理解和利用。這個演算法不是靜態的，它透過對數據的觀察，動態調整自身策略，以適應不同的數據模式。

這種設計思路提供了一個重要的啟示：在面對現實世界問題時，理論和實踐的結合往往比單純追求理論完美更為重要。

透過本文的深入分析，我們對 TimSort 的工作原理及其核心概念有了更為直觀的理解。現在，如果再次回顧它的定義，您會發現自己有了更深刻的認識。

參考資料：

[1] https://en.wikipedia.org/wiki/Timsort

[2] https://dev.to/brandonskerritt/timsort-the-fastest-sorting-algorithm-you-ve-never-heard-of-2ake

[3] https://www.infopulse.com/blog/timsort-sorting-algorithm

[4] https://juejin.cn/post/6844904131518267400

[5] https://www.youtube.com/watch?v=_dlzWEJoU7I

[6] https://www.youtube.com/watch?v=1wAOy88WxmY

WWH 系列文章列表：

[1]

[2]

[3]

[4]

[5]

[6]

[7]

最近文章列表：

[1]

[2]

[3] ？

[4] ？

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]