Timsort 是一個(gè)實(shí)際的算法，通過將組合插入和歸并算法，結(jié)合現(xiàn)實(shí)世界中數(shù)據(jù)的特征對合并策略進(jìn)行修改，最終形成一個(gè)高效且穩(wěn)定的算法。這種工程思想很值得我們學(xué)習(xí)。

除了下文提到的一些應(yīng)用，Timsort也被引入Chrome V8，成為Array.prototype.sort的默認(rèn)算法.
同時(shí)也需要注意，Timsort 需要 O(n) 的內(nèi)存空間，在實(shí)際使用時(shí)也需要考慮機(jī)器的內(nèi)存和數(shù)據(jù)的大小。

本文是一篇譯文，原文鏈接: What is Timsort Algorithm?

什么是 Timsort ?

Timsort是一種數(shù)據(jù)排序算法。它基于這種思想，即現(xiàn)實(shí)世界中的數(shù)據(jù)集幾乎總是包含有序的子序列，因此它的排序策略是識(shí)別出有序序列，并使用歸并排序和插入排序?qū)λ鼈冞M(jìn)行進(jìn)一步排序。就復(fù)雜度和穩(wěn)定性而言，Timsort是最好的排序算法之一。

與“冒泡”或“插入”排序不同，Timsort 相當(dāng)新 - 它是由 Tim Peters（以他的名字命名）于2002年發(fā)明的。并在那之后，它就成為Python、OpenJDK 7和Android JDK 1.5中的標(biāo)準(zhǔn)排序算法。這背后的緣由， 只需看看維基百科這張表就知道了。

image

在上表看似眾多的算法中，僅有七個(gè)不錯(cuò)的算法（平均或最壞情況的復(fù)雜度為O(nlogn)），其中只有兩個(gè)具有穩(wěn)定性，并且最優(yōu)情況的復(fù)雜度為O(n)。其一為 Tree sort，第二個(gè)就是 Timsort 。
該算法基于這種思想，即現(xiàn)實(shí)世界中待排序的數(shù)據(jù)集一般包含有序（非降序或降序）子數(shù)組。通常情況也確實(shí)如此。對于擁有這種特征的數(shù)據(jù)，Timsort 的執(zhí)行效率領(lǐng)先于軟件工程中的所有其他算法。

直奔主題

該算法不涉及任何復(fù)雜的數(shù)據(jù)計(jì)算。事實(shí)是，Timsort 實(shí)際上不是一個(gè)獨(dú)立的算法，而是一個(gè)由作者精心編排，由眾多算法有效組合而成的混合算法。該算法的運(yùn)行機(jī)制可以簡述如下：

1. 使用一個(gè)特定算法將輸入數(shù)組拆分為多個(gè)子數(shù)組。
2. 每個(gè)子數(shù)組都使用簡單的插入排序算法進(jìn)行排序。
3. 排序后的子數(shù)組通過歸并排序算法進(jìn)行合并。
   與其他算法類似，設(shè)計(jì)的精妙之處往往隱藏于細(xì)節(jié)之中，也就是下面要講的算法和對歸并排序的修改。

算法

定義

• N：輸入數(shù)組的長度
• run：輸入數(shù)組中的一個(gè)有序子數(shù)組，并且滿足非降序或嚴(yán)格降序，即： "a0≤a1≤a2≤…" 或 "a0> a1> a2>…"
• minrun：run 的最小長度。它的值是根據(jù)某種邏輯從 N 計(jì)算出。

image

第一步 Minrun 的計(jì)算

Minrun的值是基于N得出的，且按照以下幾個(gè)原則：

1. 它不應(yīng)該太大，因?yàn)樽訑?shù)組要進(jìn)行插入排序，而插入排序?qū)τ诙虜?shù)組更有效。
2. 它不應(yīng)該太小，否則歸并排序時(shí)合并的次數(shù)就變多。
3. 比較理想的情況是 N/minrun 等于 2 的冪次方（或接近），此時(shí)歸并排序的執(zhí)行效率最高。
   在這里，作者引用了自己的實(shí)驗(yàn)，結(jié)果表明當(dāng) minrun > 256 時(shí)，不滿足第一個(gè)原則，在 minrun < 8 時(shí)，不滿足第二個(gè)原則，并當(dāng)值在32到65之間時(shí)算法運(yùn)行效率最高。這里有個(gè)例外：當(dāng) N < 64，則 minrun = N，Timsort 變成簡單的歸并排序。到這里可以發(fā)現(xiàn) minrun 的計(jì)算算法非常簡單：只要從N中取出六個(gè)最高有效位，然后再根據(jù)剩余的位中是否有1來決定要不要加1即可。代碼大致如下所示：

int GetMinrun(int n)
{
    int r = 0;  /* becomes 1 if the least significant bits contain at least one off bit */
    while (n >= 64) {
        r |= n & 1;
        n >>= 1;
    }
    return n + r;
}

第二步 將數(shù)組分成 run 并排序

到目前為止，已經(jīng)有了一個(gè)大小為 N 的輸入數(shù)組和一個(gè)計(jì)算出來的 minrun 。該步驟的算法如下：

1. 將輸入數(shù)組的起始位置設(shè)為起始點(diǎn)。
2. 在輸入數(shù)組中搜索 run（即有序數(shù)組）。根據(jù)定義，該 run 肯定會(huì)包括當(dāng)前元素和后續(xù)的元素，但包含多少個(gè)后續(xù)的元素則是隨機(jī)的。如果該 run 是嚴(yán)格降序的，則會(huì)被轉(zhuǎn)成非降序（只需經(jīng)過簡單的數(shù)組反轉(zhuǎn)即可）。
3. 如果當(dāng)前 run 的大小小于 minrun ，則從后續(xù)元素中取 (minrun — size(run)) 個(gè)元素加入該 run。因此，一個(gè)run 最終的大小會(huì)大于或等于 minrun，其中有一部分子序列（理想情況下是全部）是有序的。
4. 然后通過插入排序算法對這個(gè)部分有序的 run 進(jìn)行排序，由于 run 的數(shù)量很小，因此算法運(yùn)行速度快且性能高。
5. 將該 run 的下一個(gè)元素所在位置設(shè)置起始點(diǎn)。
6. 如果尚未到達(dá)輸入數(shù)組的末尾，轉(zhuǎn)到第2步，否則該步驟結(jié)束。

第三步 合并

到這個(gè)階段，已經(jīng)將一個(gè)輸入數(shù)組分割成了多個(gè) run。如果輸入數(shù)組中的數(shù)據(jù)是隨機(jī)的，則 run 的大小接近 minrun；如果數(shù)據(jù)是有序的（這也是該算法期望的情況），run 的大小將超過 minrun?，F(xiàn)在，需要將這些 run 合并，并最終得到一個(gè)完全有序的數(shù)組，在此過程中，有兩個(gè)條件必須被滿足：

1. 應(yīng)該合并大小接近的 run（這樣會(huì)更有效）。
2. 算法的穩(wěn)定性需要維持，即沒有無用的調(diào)換（例如，兩個(gè)相鄰的相等的數(shù)字不應(yīng)該被交換）。
   這可以通過以下方式實(shí)現(xiàn)：
3. 創(chuàng)建一個(gè)空棧，存入第一個(gè) run。
4. 將當(dāng)前 run 也存入棧中。
5. 評估當(dāng)前的 run 是否應(yīng)與前一個(gè) run 合并。為此，需要檢查兩個(gè)條件(X,Y,Z分別為棧頂?shù)娜齻€(gè) run):

• X > Y + Z
• Y > Z

4. 如果有一個(gè)條件不滿足，則將數(shù)組 Y 與 X 和 Z 之間的最小者合并，然后繼續(xù)執(zhí)行檢查，直到兩個(gè)條件都滿足或棧為空（即所有數(shù)據(jù)均完成排序）。
5. 如果有滿足上述兩個(gè)條件的 run，轉(zhuǎn)到步驟2，存入棧中，否則結(jié)束該步驟。
   這個(gè)過程的目的是保持平衡，例如，合并的操作將如下所示：

image

因此可以看出，按這種方式操作后的 run，它的大小就比較適合下一步的歸并排序。想象一種理想的情況：一個(gè)組 run 的大小分別為 128, 64, 32, 16, 8, 4, 2 和 2（暫時(shí)忽略 minrun 的限制）。在這種情況下，前面的 run 都不會(huì)觸發(fā)合并， 直到最后兩個(gè) run ，然后從最后兩個(gè)開始將執(zhí)行七次完全平衡的合并。

Run的合并

在算法的第三步中，我們將兩個(gè)連續(xù)的 run 合并為一個(gè)有序的 run，這個(gè)合并的過程需要使用額外的內(nèi)存。具體步驟如下:

1. 創(chuàng)建一個(gè)臨時(shí)數(shù)組（臨時(shí) run），大小取自待合并的 run 中的較小者。
2. 將較小的 run 復(fù)制到臨時(shí) run（假設(shè)較小的 run 在棧底）。
3. 將臨時(shí) run 和較大的 run 的第一個(gè)元素標(biāo)記為起始位置。
4. 比較兩個(gè)起始位置的元素的大小，將較小者移到目標(biāo)數(shù)組中，并將起始位置后移。
5. 重復(fù)步驟4，直到其中一個(gè)數(shù)組的元素全部取完。
6. 將未取完的 run 中剩余的所有元素添加到目標(biāo)數(shù)組的末尾。
   注：如果較小者在棧頂，則元素的比較順序?qū)挠蚁蜃蟆?/li>

image

對歸并排序的修改

在上述歸并排序中，一切似乎都很完美。除了一種情況，想象一下這兩個(gè)數(shù)組的合并：
A = {1，2，3,…，9999，10000}
B = { 20000，20001，….，29999，30000}
上述提到的步驟也適用這種情況，但是要經(jīng)過10000次的比較和移動(dòng)。Timsort也為此提供了一種修改版本， 稱為"galloping"。
具體如下：

1. 如上所述開始?xì)w并排序。
2. 元素從臨時(shí)或較大的 run 到目標(biāo)數(shù)組的移動(dòng)將被記錄。
3. 如果有許多（在該算法的表示中，該數(shù)字為7）的元素都是從同一個(gè) run 中移出，則可以假定下一個(gè)元素也將來自相同的 run. 此時(shí) galloping 模式會(huì)被打開，即在該 run 上運(yùn)用二分查找去定位元素，用于數(shù)據(jù)對比。二分查找比線性搜索更有效，因此查找次數(shù)將會(huì)少得多。
4. 最后，當(dāng)該 run 中的元素不滿足條件時(shí)（或達(dá)到 run 的盡頭），則可以批量移動(dòng)數(shù)據(jù)（比移動(dòng)單個(gè)元素效率更高）。
   這個(gè)解釋可能有點(diǎn)模糊，我們來看一下示例：
   A = {1，2，3,…，9999，10000}
   B = {20000，20001，….，29999，30000}
5. 在前七次對比中，將 run A 中的元素 1，2，3，4，5，6 和 7 與元素 20000 進(jìn)行比較，發(fā)現(xiàn) 20000 一直都是較大者， 所以它們被從 run A 移動(dòng)到目標(biāo)數(shù)組。
6. 從下一次比較開始，galloping 模式會(huì)被打開：元素 20000 將與 run A 中的的元素 8，10，14，22，38，n+2^i，…，10000 進(jìn)行比較?？梢钥吹?，這樣比較的次數(shù)將遠(yuǎn)遠(yuǎn)少于10000。
7. 當(dāng) run A 為空時(shí)，就知道它的所有元素都比 run B 中的?。ó?dāng)然也有可能在 run A 不為空的時(shí)候停止）。 run A 中的數(shù)據(jù)將被移動(dòng)到目標(biāo)數(shù)組。

到此算法就結(jié)束了。