簡介
MergeSort對已經反向排好序的輸入時復雜度為O(n^2)，而timsort就是針對這種情況，對MergeSort進行優化而產生的，平均複雜度為n*O(log n),最好的情況為O(n)，最壞情況n*O(log n)。並且TimSort是一種穩定性排序。思想是先對待排序列進行分區，然後再對分區進行合併，看起來和MergeSort步驟一樣，但是其中有一些針對反向和大規模數據的優化處理。
歸併排序的優化思想
歸併排序有以下幾點優化方法：
和快速排序一樣，對於小數組可以使用插入排序或者選擇排序，避免遞歸調用。
在merge()調用之前，可以判斷一下a[mid]是否小於等於a[mid+1]。如果是的話那麼就不用歸併了，數組已經是有序的。原因很簡單，既然兩個子數組已經有序了，那麼a[mid]是第一個子數組的最大值，a[mid+1]是第二個子數組的最小值。當a[mid]<=a[mid+1]時，數組整體有序。
為了節省將元素複製到輔助數組作用的時間，可以在遞歸調用的每個層次交換原始數組與輔助數組的角色。
在merge()方法中的歸併過程需要判斷i和j是否已經越界，即某半邊已經用盡。可以用另一種方式，去掉檢測是否某半邊已經用盡的代碼。具體步驟是將數組a[]的後半部分以降序的方式複製到aux[]，然後從兩端歸併。對於數組{1,2,3}和{2,3,5},第一個子數組照常複製，第二個則從後往前複製，最終aux[]中的元素為{1,2,3,5,3,2}。這種方法的缺點是使得歸併排序變為不穩定排序。代碼實現如下：
void merge(int[] a, int lo, int mid, int hi, int[] aux) {for (int k = lo; k <= mid; k++) { aux[k] = a[k];}for (int k = mid + 1;k <= hi; k++) { aux[k] = a[hi - k + mid + 1];}int i = lo, j = hi; //從兩端往中間for (int k = lo; k <= hi; k++) if (aux[i] <= aux[j]) a[k] = aux[i++]; else a[k] = aux[j--];}TimSort的步驟
分區
分區的思想是掃描一次數組，把連續正序列（如果是升序排序，那麼正序列就是升序序列），或者【嚴格】（保證排序算法的穩定性）的反序列做為一個分區（run），如果是反序列，把分區裡的元素反轉一下。 例如
1，2，3，6，4，5，8，6，4 劃分分區結果為
[1,2,3,6],[4,5,8],[6,4]
然後反轉反序列
[1,2,3,6],[4,5,8],[4,6]
合併
考慮一個極端的例子，比如分區的長度分別為10000，10，1000，10，10，我們當然希望是先讓10個10合併成20， 20和1000合併成1020如此下去， 如果從從左往右順序合併的話，每次都用到10000這個數組和去小的數組合併，代價太大了。所以我們可以用一個策略來優化合併的順序。
實例
以java中的ComparableTimSort.sort()為例子， 用了一個run stack來確定是否應該合併，
if (nRemaining < MIN_MERGE) { int initRunLen = countRunAndMakeAscending(a, lo, hi); binarySort(a, lo, hi, lo + initRunLen); return; }小於MIN_MERGE（32）的排序，分區後直接用二分插入排序
int minRun = minRunLength(nRemaining); do { //找出下一個分區的起始位置，同時也對反向序列做了翻轉處理int runLen = countRunAndMakeAscending(a, lo, hi); //保證run stack中的run的都大於minRun ，如果當前分區太小，就從後面取出元素補足if (runLen < minRun) { int force = nRemaining <= minRun ? nRemaining : minRun; binarySort(a, lo, lo + force, lo + runLen); runLen = force; } //把run放入run stack中ts.pushRun(lo, runLen); //判斷是否應該合併，i是從棧頂開始的，知道不能合併為止//1. runLen[i - 3] > runLen[i - 2] + runLen[i - 1] //2. runLen[i - 2] > runLen[i - 1] ts.mergeCollapse(); lo += runLen; nRemaining -= runLen; } while (nRemaining != 0); // Merge all remaining runs to complete sort assert lo == hi; //合併剩下的run ts.mergeForceCollapse(); assert ts.stackSize == 1;在看裡面的一個比較重要的函數
/*** 如果後2個run的長度加起來比前面一個長，則使用中間位置的run和前後長度更短的run一個合併* 如果後2個run的長度加起來比前面一個短，則把後面2個run合併*/ private void mergeCollapse() { while (stackSize > 1) { int n = stackSize - 2; if (n > 0 && runLen[n-1] <= runLen[n] + runLen[n+1]) { if (runLen[n - 1] < runLen[n + 1]) n--; mergeAt(n); } else if (runLen[n] <= runLen[n + 1]) { mergeAt(n); } else { break; // Invariant is established } } }