在計(jì)算機(jī)科學(xué)的領(lǐng)域，排序算法是每位學(xué)生必學(xué)的基礎(chǔ)，而排序的需求是每位程序員在編程過(guò)程中都會(huì)遇到的。

在你輕松調(diào)用 .sort() 方法對(duì)數(shù)據(jù)進(jìn)行排序時(shí)，是否曾好奇過(guò)，這個(gè)簡(jiǎn)單的方法背后使用的是哪種排序算法呢？

本文將帶你走進(jìn) TimSort，一個(gè)在標(biāo)準(zhǔn)函數(shù)庫(kù)中廣泛使用的排序算法。

這個(gè)算法由工程師 Tim Peters 于 2001 年專(zhuān)為 Python 設(shè)計(jì)，并自 Python 2.3 版本起成為其默認(rèn)排序算法。它的影響不止于此，Java、Android、GNU Octave、Chrome 的 V8 引擎、Swift 以及 Rust 等也紛紛采用了這一算法。

那么，是什么讓 TimSort 在眾多排序算法中獨(dú)樹(shù)一幟，贏得了如此廣泛的應(yīng)用和認(rèn)可呢？

在本文中，我們將深入剖析 TimSort 的內(nèi)部機(jī)制，揭示其背后的高效實(shí)現(xiàn)原理，讓你領(lǐng)略這一算法的獨(dú)特魅力。

小規(guī)模數(shù)據(jù)的高效處理：插入排序

TimSort 是一個(gè)結(jié)合了插入排序和歸并排序的混合排序算法，特別適合處理真實(shí)世界的各種數(shù)據(jù)。

從這句定義中您可能會(huì)好奇，為什么 TimSort 選擇了插入排序和歸并排序？為什么說(shuō)它適合處理真實(shí)世界的數(shù)據(jù)？

讓我們首先探討第一個(gè)問(wèn)題，為什么插入排序成為了 TimSort 的關(guān)鍵組成部分。

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

這是因?yàn)椴迦肱判蛑簧婕皟蓚€(gè)簡(jiǎn)單操作：比較和移動(dòng)。

通過(guò)比較，我們能夠確定新元素的插入點(diǎn)；通過(guò)移動(dòng)，我們?yōu)樾略氐牟迦腧v出空間。

視頻 插入排序

關(guān)鍵在于，對(duì)于小數(shù)據(jù)集而言，n^2 與 nlogn 的差異并不顯著，復(fù)雜度不占主導(dǎo)作用，此時(shí)每輪單元的操作數(shù)量才起到?jīng)Q定性因素。得益于其簡(jiǎn)潔的操作，插入排序在小規(guī)模數(shù)據(jù)集上的表現(xiàn)通常非常出色。

但究竟什么規(guī)模的數(shù)據(jù)集算是“小”呢？

以 Python 為例，當(dāng)數(shù)據(jù)集大小小于 64 時(shí)，它會(huì)默認(rèn)采用插入排序。而在 Java 中，這一界限則被設(shè)定在了 32。

插入排序的優(yōu)化：二分插入排序

對(duì)于 TimSort 算法來(lái)說(shuō)，傳統(tǒng)插入排序也存在進(jìn)一步提升性能的空間。

回顧一下，插入排序涉及的關(guān)鍵操作有兩個(gè)：比較和移動(dòng)。這其中，對(duì)于一個(gè)數(shù)組來(lái)說(shuō)，移動(dòng)的總次數(shù)是固定不變的，因此，我們可以嘗試從減少比較的次數(shù)來(lái)優(yōu)化。

在插入排序的執(zhí)行過(guò)程中，數(shù)據(jù)被劃分為已排序和未排序的兩個(gè)部分。在已排序部分，我們尋找未排序部分下一個(gè)元素的插入位置時(shí)，常規(guī)做法是采用線(xiàn)性查找。

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

對(duì)小規(guī)模數(shù)據(jù)集而言，這種優(yōu)化尤其有效，能顯著提升排序的效率。

視頻 二分查找插入位置

舉個(gè)例子，如上面視頻所示，在使用傳統(tǒng)插入排序時(shí)，為將元素 2 插入正確位置，需要進(jìn)行 5 次比較。而在二分插入排序中，這一過(guò)程可以縮減至僅需 2 次比較，從而顯著提高排序效率。

TimSort 的工作原理

在詳細(xì)了解了插入排序在 TimSort 中的作用之后，接下來(lái)我們可以進(jìn)一步了解歸并排序在 TimSort 中的應(yīng)用。不過(guò)在這之前，我們需要知道 TimSort 的整體工作原理。

TimSort 的設(shè)計(jì)目標(biāo)是最大限度地利用在絕大多數(shù)實(shí)際數(shù)據(jù)中已經(jīng)存在的連續(xù)有序序列，這些被稱(chēng)為自然序列 natural run。

在算法的執(zhí)行過(guò)程中，它遍歷數(shù)據(jù)集，借助于這些自然序列，必要時(shí)將附近的元素添加進(jìn)去，形成一個(gè)個(gè)的數(shù)據(jù)塊 run，其中每個(gè) run 中的元素都會(huì)進(jìn)行排序。

隨后，這些有序的 run 被堆疊在一個(gè)棧中，形成了算法處理過(guò)程的一個(gè)關(guān)鍵結(jié)構(gòu)。

動(dòng)圖 run 堆疊

當(dāng)一個(gè)新的 run 被識(shí)別并加入到棧中后，TimSort 會(huì)根據(jù)棧頂多個(gè) run 的長(zhǎng)度來(lái)判斷，是否應(yīng)該合并棧頂附近的 run。

這個(gè)過(guò)程將持續(xù)進(jìn)行，直到所有數(shù)據(jù)都遍歷完。

run 合并

遍歷結(jié)束后，棧中剩余的所有 run 每次兩兩合并，直到最終形成一個(gè)完整有序的 run。

相比傳統(tǒng)歸并排序，合并預(yù)排序的 run 會(huì)大大減少了所需的比較次數(shù)，從而提升了整體的排序效率。

現(xiàn)在，你可能對(duì) TimSort 算法的細(xì)節(jié)產(chǎn)生了許多疑問(wèn)。run 是如何形成的？這些 run 是如何利用數(shù)據(jù)中已存在的自然序列？當(dāng) run 被加入到棧中后，依據(jù)什么規(guī)則來(lái)決定是否合并？……

不用擔(dān)心，接下來(lái)我們將逐一解答這些問(wèn)題，帶你更深入地理解 TimSort 算法。

計(jì)算 minrun

在 TimSort 算法中，run 的生成非常關(guān)鍵，而這一過(guò)程的核心是確定 run 最小長(zhǎng)度 minrun。這個(gè)長(zhǎng)度的設(shè)定是為了在排序過(guò)程中達(dá)到兩個(gè)關(guān)鍵目標(biāo)：

確保 run 足夠長(zhǎng)，以便有效地利用歸并排序；

避免 run 過(guò)于長(zhǎng)，從而在合并時(shí)仍能保持高效。

實(shí)驗(yàn)研究表明，當(dāng) minrun 小于 8 時(shí)，第一條原則難以滿(mǎn)足；而當(dāng) minrun 超過(guò) 256 時(shí)，第二條原則受到影響。

因此，最佳的 minrun 長(zhǎng)度范圍被確定在 32 到 64 之間。

這個(gè)范圍與我們之前提到的插入排序中小規(guī)模數(shù)據(jù)集的長(zhǎng)度范圍非常接近，這并非巧合。事實(shí)上，Timsort 在生成 run 時(shí)也會(huì)利用到插入排序。

具體計(jì)算 minrun 的方法如下：

目標(biāo)：選取一個(gè) minrun 值，以使長(zhǎng)度為 n 的數(shù)組被分割成約 n/minrun 個(gè) runs，每個(gè) run 包含大約 32 到 64 個(gè)元素。

計(jì)算方法：選擇最接近 n/(2^k) 的 minrun 值，這里 k 是使 n/(2^k) 落在32至64之間的最大整數(shù)。然后設(shè)置 minrun 為 n/(2^k)。

例如，對(duì)于長(zhǎng)度為 65 的數(shù)組，minrun 將設(shè)置為33，形成 2 個(gè)runs；對(duì)于長(zhǎng)度為 165 的數(shù)組，minrun 設(shè)置為42，形成 4 個(gè)runs。

這個(gè)計(jì)算過(guò)程涉及到 (2^k)，可以通過(guò)位移操作高效實(shí)現(xiàn)：

defget_minrun(n): #用于記錄在不斷右移過(guò)程中，n的最低位上非零位的數(shù)量 r=0 whilen>=64: #檢查n的最低位是否為1，若是，則設(shè)置r為1 r|=n&1 #向右移動(dòng)一位，相當(dāng)于n除以2 n>>=1 #返回n加上r，n是原始值的最高6位，r是表示過(guò)程中n是否有非零最低位的標(biāo)志 returnn+r

這種方法不僅保證了 minrun 的有效性，而且利用了位運(yùn)算的高效性，體現(xiàn)了 TimSort 設(shè)計(jì)的巧思。

run 的生成過(guò)程

在掌握了 minrun 的計(jì)算方法之后，我們現(xiàn)在可以探究 run 是如何生成的。

TimSort 的核心目標(biāo)是充分利用數(shù)據(jù)中已存在的連續(xù)有序序列來(lái)生成 run，但這是如何實(shí)現(xiàn)的呢？

TimSort 的處理流程可分為以下幾個(gè)關(guān)鍵步驟：

TimSort 開(kāi)始掃描整個(gè)數(shù)組，尋找連續(xù)的升序或降序序列。

如果遇到升序部分，TimSort 會(huì)持續(xù)掃描直到升序結(jié)束。

如果遇到降序部分，TimSort 會(huì)繼續(xù)掃描直到降序結(jié)束，并隨后將這部分翻轉(zhuǎn)成升序。

如果上述步驟識(shí)別的 run 未達(dá)到 minrun 長(zhǎng)度，TimSort 會(huì)繼續(xù)擴(kuò)展這個(gè) run，向數(shù)組后方遍歷，納入更多元素，直至達(dá) minrun 長(zhǎng)度。在這個(gè)階段，新加入元素的順序并不重要。

一旦擴(kuò)展完成，這個(gè)擴(kuò)展后的 run（無(wú)論其最初是否有序）都將通過(guò)插入排序進(jìn)行排序，以確保其內(nèi)部有序。

如果識(shí)別的 run 長(zhǎng)度遠(yuǎn)超 minrun，對(duì)于這些較長(zhǎng)的連續(xù)有序序列，TimSort 會(huì)保持其原始長(zhǎng)度，不進(jìn)行切割。這是因?yàn)檩^長(zhǎng)的有序序列對(duì)于減少后續(xù)合并操作的復(fù)雜度非常有利。

對(duì)于這些超長(zhǎng)的 run，通常無(wú)需進(jìn)行額外排序，除非它們是降序，這時(shí) TimSort 會(huì)先將其翻轉(zhuǎn)成升序。

通過(guò)這些策略，TimSort 能夠高效地生成一個(gè)有序的、長(zhǎng)度至少為 minrun 的 run，為后續(xù)的歸并排序過(guò)程奠定了堅(jiān)實(shí)基礎(chǔ)。

棧中 run 的合并規(guī)則

在 TimSort 算法中，每生成一個(gè)新的 run，它就會(huì)被加入到一個(gè)專(zhuān)門(mén)的棧中。

這時(shí)，TimSort 會(huì)對(duì)棧頂?shù)娜齻€(gè) run（我們稱(chēng)它們?yōu)閄、Y和Z）進(jìn)行檢查，以確保它們符合特定的合并規(guī)則：

|Z| > |Y| + |X|

|Y| > |X|

如果這些條件沒(méi)有被滿(mǎn)足，Y 就會(huì)與 X 或 Z 中較小的一個(gè)合并，并重新檢查上述條件。當(dāng)所有條件都滿(mǎn)足時(shí)，可以在數(shù)據(jù)中繼續(xù)遍歷生成新的 run。

run 合并

這種獨(dú)特的合并規(guī)則是為了實(shí)現(xiàn)什么目標(biāo)呢？

在 TimSort 的合并規(guī)則下，最終保留在棧中的每個(gè) run 的長(zhǎng)度至少等于前兩個(gè) run 的總長(zhǎng)度（由于滿(mǎn)足|Z| > |Y| + |X| 和 |Y| > |X|的規(guī)則）。

這種設(shè)計(jì)意味著，隨著時(shí)間的推移，棧中 run 的長(zhǎng)度會(huì)逐漸增大，其增長(zhǎng)方式類(lèi)似于斐波那契數(shù)列。

這種增長(zhǎng)模式的一個(gè)重要優(yōu)勢(shì)在于，它提供了一種有效的方式來(lái)平衡數(shù)據(jù)遍歷完成之后 run 的合并操作，同時(shí)避免了過(guò)于頻繁的合并。

在最理想情況下，這個(gè)棧從頂部到底部 run 的長(zhǎng)度應(yīng)該是[2,2,4,8,16,32,64,...]。這樣，從棧頂?shù)綏５椎暮喜⑦^(guò)程中，每次合并的兩個(gè) run 的長(zhǎng)度都是相等的，形成了完美的合并。

棧中 run 最理想形態(tài)

通過(guò)這些巧妙的規(guī)則，TimSort 在保證合并操作近似均衡的同時(shí)，也確保了在追求均衡和簡(jiǎn)化合并決策之間的權(quán)衡。

正如 Tim Peters 所指出的，找到一種方式來(lái)維持棧中這兩個(gè)規(guī)則，是一個(gè)極具智慧的折中選擇。

合并過(guò)程中的空間開(kāi)銷(xiāo)

了解完 TimSort 的工作原理和 run 在棧中的合并規(guī)則之后，我們現(xiàn)在來(lái)看 TimSort 中的最后一個(gè)重要環(huán)節(jié)：如何高效地運(yùn)用歸并排序？

雖然傳統(tǒng)的歸并排序也擁有 O(nlogn) 的時(shí)間復(fù)雜度，但它并不是原地排序，并且需要額外的 O(n) 空間開(kāi)銷(xiāo)，這使得它并沒(méi)有被廣泛地運(yùn)用。

當(dāng)然，也有改良過(guò)的原地歸并排序的實(shí)現(xiàn)，但它們的時(shí)間開(kāi)銷(xiāo)就會(huì)比較大。為了在效率和空間節(jié)約之間取得平衡，TimSort 采用了一種改進(jìn)的歸并排序，其空間開(kāi)銷(xiāo)遠(yuǎn)小于O(n)。

以一個(gè)具體例子來(lái)說(shuō)明：假設(shè)我們有兩個(gè)已排序的數(shù)組 [1, 2, 3, 6, 10] 和 [4, 5, 7, 9, 12, 14, 17]，目標(biāo)是將它們合并。

在這個(gè)例子中，我們可以觀(guān)察到：

第二個(gè)數(shù)組中的最小元素（4）需要插入到第一個(gè)數(shù)組的第四個(gè)位置以保持整體順序，

第一個(gè)數(shù)組中的最大元素（10）需要插入到第二個(gè)數(shù)組的第五個(gè)位置。

因此，兩個(gè)數(shù)組中的 [1, 2, 3] 和 [12, 14, 17] 已經(jīng)位于它們的最終位置，無(wú)需移動(dòng)。我們實(shí)際上需要合并的部分是 [6, 10] 和 [4, 5, 7, 9]。

在這種情況下，我們只需要?jiǎng)?chuàng)建一個(gè)大小為 2 的臨時(shí)數(shù)組，將[6, 10]復(fù)制到其中，然后在原數(shù)組中將它們與[4, 5, 7, 9]合并。

動(dòng)圖 歸并排序 優(yōu)化合并過(guò)程

這個(gè)例子展示了從前往后的合并過(guò)程。同樣，還有從后往前合并的情況：

動(dòng)態(tài)圖 歸并排序 從后往前合并

與傳統(tǒng)歸并排序相比，TimSort 在這里采用的優(yōu)化策略顯著減少了元素移動(dòng)的次數(shù)，縮短了運(yùn)行時(shí)間，并大幅降低了臨時(shí)空間的需求。

合并過(guò)程中的 galloping mode

在歸并排序過(guò)程中，通常的做法是逐個(gè)比較兩個(gè)數(shù)組中的元素，并將較小的元素依次放置到合適的位置。

然而，在某些情況下，這種方法可能涉及大量冗余的比較操作，尤其是當(dāng)一個(gè)數(shù)組中的元素連續(xù)地勝出另一個(gè)數(shù)組時(shí)。

想象一下，如果我們有兩個(gè)極端不平衡的數(shù)組：

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

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

在這種情況下，為了確定 B 中元素的正確插入點(diǎn)，我們需要進(jìn)行高達(dá) 10000 次的比較，這無(wú)疑是低效的。

如何解決這個(gè)問(wèn)題呢？

TimSort 的解決方案是引入了所謂的“躍進(jìn)模式”（galloping mode）。這種模式基于一個(gè)假設(shè)：如果一個(gè)數(shù)組中的元素連續(xù)勝出另一個(gè)數(shù)組中的元素，那么這種趨勢(shì)可能會(huì)持續(xù)下去。

TimSort 會(huì)統(tǒng)計(jì)從一個(gè)數(shù)組連續(xù)選中的元素?cái)?shù)量，一旦連續(xù)勝出次數(shù)達(dá)到了稱(chēng)為 min_gallop 的閾值時(shí)，TimSort 就會(huì)切換到躍進(jìn)模式。

在這種模式下，算法將不再逐個(gè)比較元素，而是將實(shí)施一種指數(shù)級(jí)搜索（exponential search）。以指數(shù)級(jí)的步長(zhǎng)（2^k）進(jìn)行跳躍，首先檢查位置 1 的元素，然后是位置 3 (1 + 2^1 )，接著是位置 7 (3 + 2^2)，以此類(lèi)推。

當(dāng)首次找到大于或等于比較元素的位置時(shí)，我們就將搜索范圍縮小到上一步的位置（2^(k-1) + 1）和當(dāng)前步的位置（2^k + 1）之間的區(qū)間。

在這個(gè)區(qū)間內(nèi)進(jìn)行更二分搜索，以快速定位正確的插入位置。

據(jù)開(kāi)發(fā)者的基準(zhǔn)測(cè)試，只有當(dāng)一個(gè)數(shù)組的首元素并不處于另一數(shù)組的前 7 位置時(shí)，躍進(jìn)模式才真正帶來(lái)優(yōu)勢(shì)，因此 min_gallop 的閾值為 7。

上面的步驟看起來(lái)比較復(fù)雜，我們以?xún)蓚€(gè)數(shù)組為例：

A = [1, 25, 31, 37]

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

根據(jù)之前合并過(guò)程中的空間開(kāi)銷(xiāo)原則，A 中的元素 1 是固定的，此時(shí)將25, 31, 37 移動(dòng)到臨時(shí)空間進(jìn)行合并排序。

動(dòng)圖 躍進(jìn)模式 1

在這種情況下，當(dāng) 25 在與 B 數(shù)組元素比較時(shí)連續(xù)勝出，觸發(fā)了躍進(jìn)模式。

動(dòng)圖 躍進(jìn)模式 2

算法直接跳躍到位置 15 (7 + 2^3)，發(fā)現(xiàn) 30 大于 25。

動(dòng)圖 躍進(jìn)模式 3

進(jìn)而在位置 7 和 15 之間執(zhí)行二分搜索，以找到 25 的插入點(diǎn)。

動(dòng)圖 躍進(jìn)模式 4

雖然躍進(jìn)模式在某些情況下能極大提高效率，但它并非總是最優(yōu)選擇。有時(shí)，躍進(jìn)模式可能導(dǎo)致更多的比較操作，尤其是在數(shù)據(jù)分布較為均勻時(shí)。

為了避免這種情況，TimSort采用了兩種策略：一是當(dāng)識(shí)別到躍進(jìn)模式的效率不及二分搜索時(shí)，會(huì)退出躍進(jìn)模式；二是根據(jù)躍進(jìn)模式的成功與否調(diào)整 min_gallop 值。

如果躍進(jìn)模式成功且連續(xù)選擇的元素均來(lái)自同一數(shù)組，min_gallop 值會(huì)減 1，以鼓勵(lì)再次使用躍進(jìn)模式；反之，則加 1，減少再次使用躍進(jìn)模式的可能性。

結(jié)語(yǔ)：TimSort - 數(shù)據(jù)排序的實(shí)用革新

在探索數(shù)據(jù)排序這個(gè)歷史悠久且充滿(mǎn)挑戰(zhàn)的領(lǐng)域中，TimSort 算法不僅是一項(xiàng)技術(shù)成就，更是實(shí)用性與創(chuàng)新的杰出典范。它的出現(xiàn)，不單單是算法領(lǐng)域的一個(gè)新節(jié)點(diǎn)，更是對(duì)現(xiàn)實(shí)世界復(fù)雜數(shù)據(jù)處理需求的有效回應(yīng)。

TimSort 的真正魅力不僅在于它的高效率，更在于它對(duì)實(shí)際數(shù)據(jù)特性的深入理解和利用。這個(gè)算法不是靜態(tài)的，它通過(guò)對(duì)數(shù)據(jù)的觀(guān)察，動(dòng)態(tài)調(diào)整自身策略，以適應(yīng)不同的數(shù)據(jù)模式。

這種設(shè)計(jì)思路提供了一個(gè)重要的啟示：在面對(duì)現(xiàn)實(shí)世界問(wèn)題時(shí)，理論和實(shí)踐的結(jié)合往往比單純追求理論完美更為重要。

通過(guò)本文的深入分析，我們對(duì) TimSort 的工作原理及其核心概念有了更為直觀(guān)的理解?，F(xiàn)在，如果再次回顧它的定義，您會(huì)發(fā)現(xiàn)自己有了更深刻的認(rèn)識(shí)。

參考資料：

[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