[演算法] TimSort — 以人命名的排序法
Timsort是由Tim Peters這位對Python語言貢獻良多的software engineer所發展出來的一種混合排序法，現在被Python預設的排序函數sorted()和sort()使用．
它的特點是速度快．在最佳狀況只有O(n)，平均和最糟狀況也有O(n log (n))．如果看不懂這個O(n)是啥的，沒關係，就只要知道這個排序法很厲害就行了．
因為這樣的特性，它算是個很穩定的排序法，因為我們可以認定它就是O(n log(n))來考慮效率．
說它是混合排序法，因為它採用了插入排序法(Insertion Sort)和合併排序法(Merge Sort)．
它的作法就是：
先把整個資料分成小區塊(稱作Run)，分別把小區塊的資料以Insertion Sort排序，然後再把這些區塊以Merge Sort的合併階段作法(merge function)來合併起來．
多小的區塊呢？一般建議是32到64個數值．
這個數值是2的倍數，因為merge function對於2的倍數的資料數目，處理得比較好．
會對小區塊資料用Insertion Sort來排序，也是看上Insertion Sort對少數資料的排序比較快速．
取兩個排序法的優點，就是這個TimSort的好處．
啊，上面這個動態圖動得有點快，希望你能看得懂，因為我反而看不清楚它的魔術是怎麼表演的．
反正，第一階段是用Insertion Sort對小區塊排序．
Insertion Sort就有趣了，舉個現實例子就是打撲克牌時，我們把拿到手中的牌，按照順序排列時，是把已經排好的牌擠作一堆，然後把沒按照順序的牌拿起來，插在這堆已經排好的牌前面或是後面，這樣子繼續下去，就可以把所有牌給排好．
這樣排序的好處是：因為是在原有的陣列中進行排序，也就是in-place，只需要固定額外的記憶體來複製或存放這些數值，空間複雜度是O(1)．
之後，就把這些區塊合併．合併的時候利用Merge Sort的合併方法：
TimSort在這邊有一些優化的技巧，譬如說要合併的兩個區塊Ａ和Ｂ，它並不會像是上面圖示所用的作法來先比較兩個區塊的頭一個數值，而是用Ｂ的區塊的第一個數值(Ｂ[0])用二分搜尋(binary search)在Ａ區塊找出它的插入位置，然後分析看看能不能把整個Ｂ區塊插入Ａ區塊．
當然，如果是向上面圖示的那兩個區塊，這種優化就沒轍了．
有興趣的話，可以看看Tim Peters的原始說明文件．
