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