基礎(chǔ)
如果有兩個數(shù)組已經(jīng)有序，那么可以把這兩個數(shù)組歸并為更大的一個有序數(shù)組。歸并排序便是建立在這一基礎(chǔ)上。要將一個數(shù)組排序，可以將它劃分為兩個子數(shù)組分別排序，然后將結(jié)果歸并，使得整體有序。子數(shù)組的排序同樣采用這樣的方法排序，這個過程是遞歸的。
下面是示例代碼：
#include "timsort.h"#include <stdlib.h>#include <string.h>// 將兩個長度分別為l1, l2的已排序數(shù)組p1, p2合并為一個// 已排序的目標(biāo)數(shù)組。void merge(int target[], int p1[], int l1, int p2[], int l2);void integer_timsort(int array[], int size){ if(size <= 1) return; int partition = size/2; integer_timsort(array, partition); integer_timsort(array + partition, size - partition); merge(array, array, partition, array + partition, size - partition);}void merge(int target[], int p1[], int l1, int p2[], int l2){ int *merge_to = malloc(sizeof(int) * (l1 + l2)); // 當(dāng)前掃描兩數(shù)組的位置 int i1, i2; i1 = i2 = 0; // 在合并過程中存放下一個元素的位置 int *next_merge_element = merge_to; // 掃描兩數(shù)組，將較小的元素寫入 // merge_to. 當(dāng)兩數(shù)相等時我們選擇 // 左邊的, 因為我們想保證排序的穩(wěn)定性 // 當(dāng)然對于integers這無關(guān)緊要，但這種想法是很重要的 while(i1 < l1 && i2 < l2){ if(p1[i1] <= p2[i2]){ *next_merge_element = p1[i1]; i1++; } else { *next_merge_element = p2[i2]; i2++; } next_merge_element++; } // 如果有一個數(shù)組沒有掃描完，我們直接拷貝剩余的部分 memcpy(next_merge_element, p1 + i1, sizeof(int) * (l1 - i1)); memcpy(next_merge_element, p2 + i2, sizeof(int) * (l2 - i2)); // 現(xiàn)在我們已經(jīng)將他們合并在了我們的額外的存儲空間里了 // 是時候轉(zhuǎn)存到target了 memcpy(target, merge_to, sizeof(int) * (l1 + l2)); free(merge_to);}#include "timsort.h"#include <stdlib.h>#include <string.h> // 將兩個長度分別為l1, l2的已排序數(shù)組p1, p2合并為一個// 已排序的目標(biāo)數(shù)組。void merge(int target[], int p1[], int l1, int p2[], int l2); void integer_timsort(int array[], int size){ if(size <= 1) return; int partition = size/2; integer_timsort(array, partition); integer_timsort(array + partition, size - partition); merge(array, array, partition, array + partition, size - partition);} void merge(int target[], int p1[], int l1, int p2[], int l2){ int *merge_to = malloc(sizeof(int) * (l1 + l2)); // 當(dāng)前掃描兩數(shù)組的位置 int i1, i2; i1 = i2 = 0; // 在合并過程中存放下一個元素的位置 int *next_merge_element = merge_to; // 掃描兩數(shù)組，將較小的元素寫入 // merge_to. 當(dāng)兩數(shù)相等時我們選擇 // 左邊的, 因為我們想保證排序的穩(wěn)定性 // 當(dāng)然對于integers這無關(guān)緊要，但這種想法是很重要的 while(i1 < l1 && i2 < l2){ if(p1[i1] <= p2[i2]){ *next_merge_element = p1[i1]; i1++; } else { *next_merge_element = p2[i2]; i2++; } next_merge_element++; } // 如果有一個數(shù)組沒有掃描完，我們直接拷貝剩余的部分 memcpy(next_merge_element, p1 + i1, sizeof(int) * (l1 - i1)); memcpy(next_merge_element, p2 + i2, sizeof(int) * (l2 - i2)); // 現(xiàn)在我們已經(jīng)將他們合并在了我們的額外的存儲空間里了 // 是時候轉(zhuǎn)存到target了 memcpy(target, merge_to, sizeof(int) * (l1 + l2)); free(merge_to);}我不會總是貼出完整的代碼~
優(yōu)化
現(xiàn)在，如果你是一個C程序員，你可能已經(jīng)在吐槽了：我在每次合并過程中都申請并釋放了一次額外存儲空間（你可能也會不爽于我沒有檢查返回值是否為null,請無視之…如果這能讓你感覺好一點）
這個問題只要一點點的改動就可以修正：
void merge(int target[], int p1[], int l1, int p2[], int l2, int storage[]);void integer_timsort_with_storage(int array[], int size, int storage[]);void integer_timsort(int array[], int size){ int *storage = malloc(sizeof(int) * size); integer_timsort_with_storage(array, size, storage); free(storage);}void merge(int target[], int p1[], int l1, int p2[], int l2, int storage[]);void integer_timsort_with_storage(int array[], int size, int storage[]); void integer_timsort(int array[], int size){ int *storage = malloc(sizeof(int) * size); integer_timsort_with_storage(array, size, storage); free(storage);}現(xiàn)在我們有了排序函數(shù)的最頂層，做了一些內(nèi)存分配（setup）工作并將其傳入調(diào)用中。這是我們將要開始優(yōu)化工作的模版，當(dāng)然最后實際可用的版本會更加復(fù)雜而不僅僅是優(yōu)化一塊內(nèi)存空間。
現(xiàn)在我們有了基本的歸并排序了，我們需要想想：我們能怎樣來優(yōu)化它？
一般來說我們不能指望對于每一種情況都能達(dá)到最優(yōu)。歸并排序的性能已經(jīng)很接近比較排序的下界了。timsort的關(guān)鍵特性是極好的利用了數(shù)據(jù)中存在的規(guī)律。如果數(shù)據(jù)中存在普遍的規(guī)律，我們應(yīng)該盡可能的利用他們，如果沒有，我們的算法應(yīng)該保證不會比普通的歸并排序差太多。
如果你看過歸并排序的實現(xiàn)，你會發(fā)現(xiàn)其實所有的工作都是在合并（merge）的過程當(dāng)中完成的。所以優(yōu)化的重點也就落在了這里。由此我們得出以下三點可能的優(yōu)化途徑：
1、能否使合并過程運行的更快？
2、能否執(zhí)行更少的合并過程？
3、是否存在一些與其使用歸并排序不如使用其他排序的情況？
以上三個問題的答案都是肯定的，并且這也是對歸并排序進(jìn)行優(yōu)化最為普遍的途徑。舉例來說，遞歸的實現(xiàn)使得根據(jù)數(shù)組的規(guī)模使用不同的排序算法變的非常簡單。歸并排序是一個很好的通用性排序算法，（具有很好的漸進(jìn)復(fù)雜度）但對小數(shù)組而言常數(shù)因子就顯得愈發(fā)重要，當(dāng)數(shù)組的大小小于某個值時（通常是7或者8左右）歸并排序的性能頻繁的低于插入排序。
這并不是timsort的原理，但是我們之后會用到插入排序，所以我們先開個小差。
最簡單的：假設(shè)我們有一個具有n個元素的已排序數(shù)組，并且在尾端有第n+1個元素的位置。現(xiàn)在我們想要向里面添加一個新的元素并保持?jǐn)?shù)組有序。我們需要為新元素找到一個合適的位置并將比它大的數(shù)向后移動。一種顯而易見的做法是將新元素放到第n+1個位置上，然后從后向前兩兩交換直到到達(dá)正確的位置（對較大的數(shù)組這并不是最好的做法：你可能想要對數(shù)據(jù)進(jìn)行二分查找（binary search）然后把剩下的元素不做比較的向后移動。但是對小數(shù)組來說這樣的做法反而不是很好，due to cache effects）
這就是插入排序工作的方式：當(dāng)你有了k個已排序的元素，將第k+1個元素插入其中，你就有了k+1個已排序的元素。反復(fù)如此直到整個數(shù)組有序。
下面是代碼：
void insertion_sort(int xs[], int length){ if(length <= 1) return; int i; for(i = 1; i < length; i++){ // i之前的數(shù)組已經(jīng)有序了，現(xiàn)在將xs[i]插入到里面 int x = xs[i]; int j = i - 1; // 將j向前移動直到數(shù)組頭或者 // something <= x, 并且其右邊的所有的元素都已經(jīng) // 右移了 while(j >= 0 && xs[j] > x){ xs[j+1], xs[j]; j--; } xs[j+1] = x; }}void insertion_sort(int xs[], int length){ if(length <= 1) return; int i; for(i = 1; i < length; i++){ // i之前的數(shù)組已經(jīng)有序了，現(xiàn)在將xs[i]插入到里面 int x = xs[i]; int j = i - 1; // 將j向前移動直到數(shù)組頭或者 // something <= x, 并且其右邊的所有的元素都已經(jīng) // 右移了 while(j >= 0 && xs[j] > x){ xs[j+1], xs[j]; j--; } xs[j+1] = x; }}現(xiàn)在排序的代碼會被修改為下面這樣：
void integer_timsort_with_storage(int array[], int size, int storage[]){ if(size <= INSERTION_SORT_SIZE){ insertion_sort(array, size); return; }}void integer_timsort_with_storage(int array[], int size, int storage[]){ if(size <= INSERTION_SORT_SIZE){ insertion_sort(array, size); return; }}你可以在這里查看這個版本
好了，讓我們回歸正題：優(yōu)化歸并排序。
能否執(zhí)行更少的合并過程？
對于一般的情況，不行。但是讓我們考慮一些普遍存在的情況。
假設(shè)我們有一個已經(jīng)排好序的數(shù)組，我們需要執(zhí)行多少次合并過程？
原則上來說1次也不需要：數(shù)組已經(jīng)排好序了，不需要做任何多余的工作。所以一個可行的選擇是增加一個初始的檢查來確定數(shù)組是否已經(jīng)排好序了并在確認(rèn)之后立刻退出。
但是那樣會給排序算法增加很多額外的計算，雖然在判斷成功的情況下帶來很大的收益（將O(nlog(n))的復(fù)雜度下降到O(n)），但是如果判斷失敗了，會造成很多無用的計算。下面讓我們看看我們該怎樣實現(xiàn)這種檢查并且無論其失敗與否都能將檢查的結(jié)果很好的利用起來。
假設(shè)我們遇到了下面的數(shù)組：
{5, 6, 7, 8, 9, 10, 1, 2, 3}（現(xiàn)在暫且忽略我們會對小于n的數(shù)組使用不同的排序方法）
為了得到最好的合并策略，我們應(yīng)該在哪里進(jìn)行分段呢？
顯然在這里有兩個已經(jīng)排好序的子數(shù)組：5到10和1到3，如果選擇這兩段作為分段必然可以獲得很好的效果。
接下來提出一種片面的方法：
找出初始狀態(tài)下最長的上升序列作為第一個分段（partition）,剩余部分作為第二個分段。
當(dāng)數(shù)據(jù)是由不多的幾個已排序的數(shù)組組成的情況下，這種方法表現(xiàn)的很好，但是這種方法存在十分糟糕的最差情況。考慮一個完全逆序的數(shù)組，每次分段的第一段都只有一個數(shù)，所以在每次遞歸中第一段只有一個數(shù)，而要對第二段的n-1個元素進(jìn)行遞歸的歸并排序。這造成了明顯不令人滿意的O(n^2)的性能表現(xiàn)。
我們也可以人工的將過短的分段修改為總長度一半的元素以避免這個問題，但是這同樣也是不令人滿意的：我們額外的檢查工作基本沒有什么收益。
但是，基本的思路已經(jīng)明確了：利用已經(jīng)有序的子序列作為分段的單位。
困難的是第二段的選擇，為了避免出現(xiàn)糟糕的最差情況，我們需要保證我們的分段是盡可能的平衡的。
讓我們退一步看看是否有辦法改正它。考慮下面這種有些奇怪的對普通歸并排序工作過程的逆向思考：
將整個數(shù)組切分成很多長度為1的分區(qū)。
當(dāng)存在多個分區(qū)時，奇偶交替的兩兩合并這些分區(qū)（alternating even/odd）并用合并后的分區(qū)替代原先的兩個分區(qū)。
舉例來說，如果我們有數(shù)組｛1, 2, 3, 4｝那么我們會這么做：
{{1}, {2}, {3}, {4}}{{1, 2}, {3, 4}}{{1, 2, 3, 4}}很容易觀察到這和普通歸并排序的做法是相同的：我們只是將遞歸的過程變的明確并且用額外的存儲空間取代了棧。但是，這樣的方法更直觀的展現(xiàn)了我們應(yīng)該如何使用存在的已排序子序列：在第一步中，我們不將數(shù)組分割為長度為1的分段，而是將其分割成很多已排序的分段。然后對這些分段以相同的方法執(zhí)行合并操作。
現(xiàn)在這個方法只有一個小問題了：我們使用了一些并不需要使用的額外空間。普通的歸并排序使用了O(log(n))的棧空間。這個版本使用了O(n)的空間來存儲初始的分段情況。
那么為什么我們“等價的”算法卻有極為不同的空間消耗？
答案是我在他們的“等價”上面撒謊了。這種方法與普通的歸并排序最大的不同在于：普通歸并排序在分段操作上是“惰性”的，只有在需要生成下一級時才會生成足夠的分段并且在生成了下一級之后就會立刻的丟棄這些分段。
換句話說，我們其實是在歸并的過程中邊合并邊生成分段而不是事先就生成了所有的分段。
現(xiàn)在，讓我們看看能否將這種想法轉(zhuǎn)換成算法。
在每一步中，生成一個新的最低級的分段（在普通歸并排序中這是一個單獨的元素，在我們的上面敘述的版本中這是一個已排序的子序列）。把它加入到一個存儲分段的棧中，并且不時的合并棧頂?shù)膬蓚€分段以減小棧的大小。不停的重復(fù)這樣的動作直到?jīng)]有新的分段可以生成。然后將整個堆棧中的分段合并。
上面的算法還有一個地方?jīng)]有具體說明：我們完全沒有說明何時來執(zhí)行合并操作。
到此為止已經(jīng)有太多的文字而代碼太少了，所以我打算給出一個暫時的答案：隨便什么時候（好坑爹）。
現(xiàn)在，我們先寫一些代碼。
// 我們使用固定的棧大小，這個大小要遠(yuǎn)遠(yuǎn)大于任何合理的棧高度// 當(dāng)然，我們?nèi)匀恍枰獙σ绯鲞M(jìn)行檢查#define STACK_SIZE 1024typedef struct { int *index; int length;} run;typedef struct { int *storage; // 存儲已經(jīng)得到的分段(runs,原文作者將得到分段叫做run) run runs[STACK_SIZE]; // 棧頂指針，指向下一個待插入的位置 int stack_height; // 保持記錄我們已經(jīng)分段到哪里里，這樣我們可以知道在哪里開始下一次的分段 // 數(shù)組中index < partioned_up_to 是已經(jīng)分段并存儲在棧上的, 而index >= partioned_up_to // 的元素是還沒有存儲到棧上的. 當(dāng)partitioned_up_to == 數(shù)組長度的時候所有的元素都在棧上了 int *partitioned_up_to; int *array; int length;} sort_state_struct;typedef sort_state_struct *sort_state;// 我們使用固定的棧大小，這個大小要遠(yuǎn)遠(yuǎn)大于任何合理的棧高度// 當(dāng)然，我們?nèi)匀恍枰獙σ绯鲞M(jìn)行檢查#define STACK_SIZE 1024 typedef struct { int *index; int length;} run; typedef struct { int *storage; // 存儲已經(jīng)得到的分段(runs,原文作者將得到分段叫做run) run runs[STACK_SIZE]; // 棧頂指針，指向下一個待插入的位置 int stack_height; // 保持記錄我們已經(jīng)分段到哪里里，這樣我們可以知道在哪里開始下一次的分段 // 數(shù)組中index < partioned_up_to 是已經(jīng)分段并存儲在棧上的, 而index >= partioned_up_to // 的元素是還沒有存儲到棧上的. 當(dāng)partitioned_up_to == 數(shù)組長度的時候所有的元素都在棧上了 int *partitioned_up_to; int *array; int length; } sort_state_struct; typedef sort_state_struct *sort_state;我們將會給需要的所有函數(shù)傳入 sort_state的指針
這個排序的基礎(chǔ)邏輯代碼如下：
while(next_partition(&state)){ while(should_collapse(&state)) merge_collapse(&state);}while(state.stack_height > 1) merge_collapse(&state);while(next_partition(&state)){ while(should_collapse(&state)) merge_collapse(&state);}while(state.stack_height > 1) merge_collapse(&state);next_partition函數(shù)如果還有未入棧的元素則將一個新的分段壓入棧中并返回1，否則返回0。然后適當(dāng)?shù)膲嚎s棧。最后當(dāng)全部數(shù)組都分段完畢后將整個棧壓縮。
現(xiàn)在我們有了第一個適應(yīng)性版本的歸并排序：如果數(shù)組中有很多有序的子序列，我們就可以走一個很好的捷徑。如果沒有，我們的算法依然有（期望）O(nlog(n))的時間效率。
這個“期望”的效率有點不靠譜，在隨機(jī)的情況下我們需要一個好的策略來控制合并的過程。
我們來想一想是否有更好的限制條件。一個自然的想法來實現(xiàn)這個事情是在棧上維持一個不變式，不斷的執(zhí)行合并直到不變式滿足為止。
更進(jìn)一步，我們想要這個不變式來維持這個棧中最多只能有l(wèi)og(n)個元素
我們來考慮下面這個不變式：每個棧上的元素的長度必須>=兩倍于其之下的元素長度，所以棧頂元素是最小的，第二小的是棧頂元素的下一個元素，并且至少是棧頂元素的兩倍長度。
這個不變式確實保證了棧中l(wèi)og(n)個元素的要求，但是卻造成了將每次棧的壓縮變得很復(fù)雜的趨勢，考慮棧中元素長度如下的情況：
64, 32, 16, 8, 4, 2, 1
假設(shè)我們將一個長度為1的分段放到棧上，就會產(chǎn)生如下的合并：
64, 32, 16, 8, 4, 2, 1, 164, 32, 16, 8, 4, 2, 264, 32, 16, 8, 4, 464, 32, 16, 8, 864, 32, 16, 1664, 32, 3264, 64128
在之后對合并過程做了更多的優(yōu)化后，這種情況會顯得愈發(fā)糟糕（basically because it stomps on certain structure that might be present in the array）。但是現(xiàn)在我們的合并過程還是很簡單的，所以我們沒有必要擔(dān)心它，先暫時這樣做就可以了。
有一件值得注意的事情：我們現(xiàn)在可以確定我們棧的大小了。假設(shè)棧頂元素的長度為1，第二個元素長度必然>=2，之后的必然>=4…所以棧中元素的總長度是2^n-1, 因為在64位機(jī)器中在數(shù)組中最多只會有2^64個元素（這是一個相當(dāng)驚人的數(shù)組），所以我們的棧只需要最多65個元素，另外留出一個位置給新進(jìn)棧的元素，則我們需要分配66的空間給棧以保證永遠(yuǎn)不會出現(xiàn)overflow的情況。
另外還有一點值得注意，我們只需要檢查棧頂下面的一個元素長度>=2 * 棧頂元素長度，因為我們在入棧過程中總是保持這個不變式的，并且合并過程只會影響到棧頂兩個元素。
為了滿足不變式，我們現(xiàn)在將 should_collapse函數(shù)修改如下：
int should_collapse(sort_state state){ if (state->stack_height <= 2) return 0; int h = state->stack_height - 1; int head_length = state->runs[h].length; int next_length = state->runs[h-1].length; return 2 * head_length > next_length;}int should_collapse(sort_state state){ if (state->stack_height <= 2) return 0; int h = state->stack_height - 1; int head_length = state->runs[h].length; int next_length = state->runs[h-1].length; return 2 * head_length > next_length;}現(xiàn)在，我們的適應(yīng)性歸并排序完成了，贊！
回過頭看之前出過問題的一個例子現(xiàn)在會如何。
考慮下面的逆序數(shù)組：
5, 4, 3, 2, 1
當(dāng)使用我們的適應(yīng)性歸并排序會發(fā)生什么？
棧的運行過程如下：
{5}{5}, {4}{4, 5}{4, 5}, {3}{4, 5}, {3}, {2}{4, 5}, {2, 3}{2, 3, 4, 5}{2, 3, 4, 5}, {1}{1, 2, 3, 4, 5}這是一個足夠清晰的合并策略了。
但是還有一個更好的辦法來對逆序的數(shù)組進(jìn)行排序：直接將其原地反轉(zhuǎn)。
可以很簡單的修改我們的算法來利用到這一點，我們已經(jīng)尋找了遞增的子序列，當(dāng)找不遞增的子序列的時候可以很簡單的尋找一個遞減的子序列，然后將其反轉(zhuǎn)為一個遞增的序列加入棧中。
根據(jù)上面的策略我們修改找序列的代碼如下：
if(next_start_index < state->array + state->length){ if(*next_start_index < *start_index){ // We have a decreasing sequence starting here. while(next_start_index < state->array + state->length){ if(*next_start_index < *(next_start_index - 1)) next_start_index++; else break; } // Now reverse it in place. reverse(start_index, next_start_index - start_index); } else { // We have an increasing sequence starting here. while(next_start_index < state->array + state->length){ if(*next_start_index >= *(next_start_index - 1)) next_start_index++; else break; } }}if(next_start_index < state->array + state->length){ if(*next_start_index < *start_index){ // We have a decreasing sequence starting here. while(next_start_index < state->array + state->length){ if(*next_start_index < *(next_start_index - 1)) next_start_index++; else break; } // Now reverse it in place. reverse(start_index, next_start_index - start_index); } else { // We have an increasing sequence starting here. while(next_start_index < state->array + state->length){ if(*next_start_index >= *(next_start_index - 1)) next_start_index++; else break; } }}和基本的逆序序列相同，我們的排序現(xiàn)在也可以很好的處理混合的情況了。比如下面這種數(shù)組：
{1, 2, 3, 4, 5, 4, 3, 2, 1}執(zhí)行排序過程如下：
{1, 2, 3, 4, 5}{1, 2, 3, 4, 5}, {1, 2, 3, 4}{1, 1, 2, 2, 3, 3, 4, 4, 5}這樣的情況比我們之前的實現(xiàn)又要好上很多！
最后我們還要給算法加上一點優(yōu)化：
在我們之前的歸并排序中有存在一個臨界點以便對于小數(shù)組轉(zhuǎn)換為插入排序，但在目前我們的適應(yīng)性版本中沒有這樣的設(shè)置，這意味著如果在沒有很多特殊結(jié)構(gòu)可利用的數(shù)組中我們的性能可能要低于普通的歸并排序。
回頭想想之前那個反轉(zhuǎn)的歸并排序的過程，將小數(shù)組改用插入排序的做法可以這樣理解：比起從1的長度開始劃分，我們從 INSERTION_SORT_SIZE開始劃分，并使用插入排序來確保這一段是有序的。
這提示了我們一個自然的思路來改進(jìn)我們的適應(yīng)性版本：當(dāng)我們發(fā)現(xiàn)一個分段要小于一個設(shè)定值時，可以使用插入排序來將它增長到設(shè)定長度。
這使得我們更改了 next_partition函數(shù)的最后面的代碼如下：
if(run_to_add.length < MIN_RUN_SIZE){ boost_run_length(state, &run_to_add);}state->partitioned_up_to = start_index + run_to_add.length;if(run_to_add.length < MIN_RUN_SIZE){ boost_run_length(state, &run_to_add);}state->partitioned_up_to = start_index + run_to_add.length;boot_run_length函數(shù)如下：void boost_run_length(sort_state state, run *run){ // Need to make sure we don't overshoot the end of the array int length = state->length - (run->index - state->array); if(length > MIN_RUN_SIZE) length = MIN_RUN_SIZE; insertion_sort(run->index, length); run->length = length;}void boost_run_length(sort_state state, run *run){ // Need to make sure we don't overshoot the end of the array int length = state->length - (run->index - state->array); if(length > MIN_RUN_SIZE) length = MIN_RUN_SIZE; insertion_sort(run->index, length); run->length = length;}這將算法應(yīng)用在隨機(jī)數(shù)據(jù)上時的性能表現(xiàn)提高到了一個和普通歸并排序相比相當(dāng)具有競爭力的程度。
到這里我們終于得到了一個適應(yīng)性歸并排序，一定程度上可以說是timsort的核心部分。
新聞熱點
疑難解答
圖片精選
