簡介
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}。這種方法的缺點是使得歸并排序變為不穩定排序。代碼實現如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
|
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來確定是否應該合并，
|
1
2
3
4
5
|
if (nRemaining < MIN_MERGE) { int initRunLen = countRunAndMakeAscending(a, lo, hi); binarySort(a, lo, hi, lo + initRunLen); return;} |
小于MIN_MERGE（32）的排序，分區后直接用二分插入排序
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
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; |
在看里面的一個比較重要的函數
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
/*** 如果后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 } } } |
