作者：周秉誼 / Tomofun 資深技術經理
排序(Sorting)是一個最基本也是最常被使用的演算法，幾乎所有的程式語言都有提供排序的函式。在目前官方的CPython中，list的排序演算法從2.3版之後改為使用Timsort。本文將分享Timsort的中心概念及CPython中Timsort的幾個最佳化技巧，說明為什麼Timsort會是大家認為最適合Python的排序演算法。
前言
Python是非常容易學習的程式語言，不只可以運用在日常工作的自動化，也可以作為網路服務的後端(Backend)程式，也有豐富的標準函式庫(Python Standard Library)和套件(Package)，使得Python成為多種使用情境下都可以使用的程式語言。
除了友善的學習曲線之外，Python也在彈性和程式效能之間達到平衡。排序(Sorting)是一個最基本也是最常被使用的演算法，幾乎所有的程式語言都有提供排序的函式可供程式設計人員使用，因應各個程式語言的特性，不同語言的排序函式也會採用不同的排序演算法。如C語言stdlib中的qsort()函式是使用Quick Sort演算法，C++語言STL中的std::sort()函式是使用Introsort等等。在目前官方的CPython中，list的排序函式則是使用了Timsort排序演算法。
排序演算法性質
不同的排序演算法會有不同的特性，通常會從幾個面向來探討，包括了時間複雜度 (Time complexity)、空間複雜度(Space complexity)、穩定性 (Stability)、自適應排序(Adaptive sort)等。時間複雜度用來評量排序演算法處理大量資料時所需要的時間，一般以比較(Comparison)為主的排序演算法的時間複雜度多為O(nlogn)或O(n^2)，從時間複雜度可以了解花費的時間隨資料量上升時的變化，時間複雜度又可以分為最佳時間(Best time)、平均時間(Average time)和最差時間(Worst time)三個面向。空間複雜度可以視為額外的記憶體使用量，一般排序演算法多為O(1)、O(logn)或O(n)。穩定性指的是相同大小的不同物件在排序之後，可不可以維持原本在陣列中的前後關係，如果可以則稱這個排序演算法是穩定的(Stable)，反之則是不穩定的(Unstable)，穩定的排序演算法通常會有較好的使用性，但也要花費較多的計算和記憶體成本。自適應排序法可以利用陣列中已經排序好的特性，減少所需要的計算時間，而有較佳的最佳計算時間。
|
|
Best time
|
Average time
|
Worst time
|
Space
|
Stable
|
|
Quick Sort
|
O(n log n)
|
O(n log n)
|
O(n^2)
|
O(log n)
|
No
|
|
Merge Sort
|
O(n log n)
|
O(n log n)
|
O(n log n)
|
O(n)
|
Yes
|
|
Introsort
|
O(n log n)
|
O(n log n)
|
O(n log n)
|
O(log n)
|
No
|
|
Insertion sort
|
O(n)
|
O(n^2)
|
O(n^2)
|
O(1)
|
Yes
|
|
Timsort
|
O(n)
|
O(n log n)
|
O(n log n)
|
O(n)
|
Yes
|
圖1.排序演算法比較
Timsort
Timsort是由Tim Peters在2002年時開發出來，在Python 2.3版之後，就取代原有的Samplesort，成為Python內建的排序演算法。Timsort是混合了合併排序法(Merge Sort)及插入排序法(Insertion Sort)的一種混合排序法(Hybrid sorting)，也是一種穩定排序法及自適應排序法。經過分析和實際測試，Timsort在多種日常常見的情境當中有非常好的效能，也有其他程式語言採用。Timsort的中心概念有兩個部份，首先將資料分成一個個minrun大小的run，對每個run以插入排序法進行排序；再將各個排序好的run以類似合併排序法的合併過程合併後，就完成陣列的排序了。
timsort(a, n):
for (i=0;i<n;i+=MINRUN)
insertion_sort(a, i, i+MINRUN);
for (runsize=MINRUN;runsize<n;runsize*=2) {
for (left=0;left<n;left+=2*runsize) {
mid = left + runsize -1;
right = left + 2*runsize -1;
merge(a, left, mid, right);
}
}
圖2.Timsort排序演算法
Timsort最佳化技巧
除了基本的中心概念之外，CPython中的Timsort還做了幾個不同的技巧來加速排序，包括minrun大小的最佳化、以Binary Insertion Sort取代插入排序法、節省Merge時的記憶體使用等等。
在CPython的Timsort中，minrun的大小是由陣列的大小n來計算出來的，介於32和64之間，選擇一個令n/minrun等於二冪次方的minrun；如果無法剛好等於，就選小於二冪次方中最接近的一個minrun。而如果n小於64，則直接以n做為minrun來進行插入排序。
對每個run使用插入排序法是Timsor的一個關鍵，雖然在演算法分析上插入排序法平均的時間複雜度是O(nlogn)，但是插入排序法有良好的自適應特性，對已有部份排序的資料可以提升到O(kn)，而且在小資料量的情況之下，其他排序演算法的計算成本很難低於插入排序法。而CPython的Timsort更使用Binary Insertion Sort取代插入排序法，最主要的原因就是要節省比較的次數。Binary Insertion Sort是使用二元搜尋(Binary search)花費O(logn)的比較來找到插入的位置，相較於插入排序法是使用線性搜尋(Linear search)花費O(n)的比較，但在插入後都是要做O(n)次的資料搬移。這個特性剛好在Python中十分有利，因為Python的list中的每一個元素都是一個物件，這些物件的型別(Typing)可能非常不同，因此一個基本的比大小就需要大量的計算成本；相對來說，list中的物件搬移就只是C語言中指標(Pointer)的搬移，比起不同型別間的比大小要單純得多了。所以節省比較次數是CPython的Timsort能有較佳效能的一個關鍵。
要在合併排序中以線性時間、不花費額外記憶體進行合併，在理論上是做得到，但實務上計算的成本會非常高。因此CPython的Timsort在進行合併的時候還是會使用到額外的記憶體當暫存空間，但是在合併相鄰的A、B兩個run時搬移之前，會先在A run中搜尋B[0]的位置A[x]，則A[0:x-1]元素都不需要搬移，相似的做法也可以應用在B run中搜尋A[-1]的位置B[y]，則B[y+1:-1]間的元素也已經在正確的位置上了。
結語
在CPython的程式碼中，留有Timsort作者Tim Peters在開發Timsort時的實驗結果，針對隨機序列、遞增序列、遞減序列、幾乎排序好的序列等各種輸入序列的情境進行測試，結果中發現Timsort對於幾乎排序好的序列，比起原本的Samplesort節省了非常多的比較次數。總結來說，CPython的Timsort是一個以節省比較次數來提高效能的排序演算法，這個特性在Python的list排序中，可以省去大量未知型別物件間的比較，進而提升排序的效能。這也是為什麼Timsort會是目前大家認為最適合Python的排序演算法。
參考資料