Timsort 是一種對真實資料非常有效的排序算法。Tim Peters 在 2001 年為 Python 程式設計語言創造了 Timsort。Timsort 首先分析它要排序的清單，然後基于該分析選擇合理方案。
Timsort 自發明以來，就成為 Python、Java 、Android 平台和 GNU Octave 的預設排序算法。
圖源：http://bigocheatsheet.com/
Timsort 的排序時間與 Mergesort 相近，快于其他大多數排序算法。Timsort 實際上借鑒了插入排序和歸并排序的方法，後文将詳細介紹它的具體過程。
Peters 設計 Timsort 是為了利用大量存在于現實資料集中的有序元素，這些有序元素被稱為「natural runs」。總而言之，Timsort 會先周遊所有資料并找到資料中已經排好序的分區，且每一個分區可以稱為一個 run，最後再按規則将這些 run 歸并為一個。
數組中元素少于 64 個
如果排序的數組中元素少于 64 個，那麼 Timsort 将執行插入排序。插入排序是對小型清單最有效的簡單排序，它在大型清單中速度很慢，但是在小型清單中速度很快。插入排序的思路如下：
● 逐個檢視元素
● 通過在正确的位置插入元素來建立排序清單
下面的跟蹤表說明了插入排序如何對清單 [34, 10, 64, 51, 32, 21] 進行排序的：
天然有序的區塊：run
如果清單大于 64 個元素，則 Timsort 算法首先周遊清單，查找「嚴格」升序或降序的部分（Run）。如果一個部分遞減，Timsort 将逆轉這個部分。是以，如果 run 遞減，則如下圖所示（run 用粗體表示）：
minrun 的大小是根據數組大小确定的。Timsort 算法選擇它是為了使随機數組中的大部分 run 變成 minrun。當 run N 的長度等于或略小于 2 的倍數時，歸并 2 個數組更加高效。Timsort 選擇 minrun 是為了確定 minrun 等于或稍微小于 2 的倍數。
該算法選擇 minrun 的範圍為 32 ~ 64。當除以 minrun 時，使原始數組的長度等于或略小于 2 的倍數。
如果 run 的長度小于 minrun，則計算 minrun 減去 run 的長度。我們可以将 run 之外的新元素（minrun - run 個）放到 run 的後面，并執行插入排序來建立新的 run，這個新的 run 長度和 minrun 相同。
如果 minrun 是 63，而 run 的長度是 33，那麼可以擷取 63 - 33 = 30 個新元素。然後将這 30 個新元素放到 run 的末尾并作為新的元素，是以 run 的第 34 個元素 run[33] 有 30 個子元素。最後隻需要對後面 30 個元素執行一個插入排序就能建立一個長度為 63 的新 run。
在這一部分完成之後，現在應該在一個清單中有一系列已排序的 run。
歸并
Timsort 現在需要執行歸并排序來合并 run，需要確定在歸并排序的同時保持穩定和平衡。為了保持穩定，兩個等值的元素不應該交換，這不僅保持了它們在清單中的原始位置，而且使算法更快。
當 Timsort 搜尋到 runs 時，它們會被添加到堆棧中。一個簡單的堆棧是這樣的：
想象一堆盤子。你不能從底部取盤子，必須從頂部取，堆棧也是如此。
當歸并不同的 run 時，Timsort 試圖平衡兩個互相沖突的需求。一方面，我們希望盡可能地延遲歸并，以便利用之後可能出現的模式。但我們更希望盡快歸并，以利用剛才發現的在記憶體層級中仍然排名很高的 run。我們也不能「過分」延遲合并，因為它記住未合并的運作需要消耗記憶體，而堆棧的大小是固定的。
為了得到折衷方案，Timsort 追蹤堆棧上最近的三個項，并為這些堆棧項建立了兩個必須保持為 True 的規則：
- A > B + C
- B > C
其中 A、B 和 C 是堆棧中最近的三個項。
用 Tim Peters 自己的話來說：
一個好的折衷方案是在堆棧項上維護兩個不變量，其中 A、B 和 C 是最右邊三個還未歸并片段的長度。
通常，将不同長度的相鄰 run 歸并在一起是很難的。更困難的是還必須要保持穩定。為了解決這個問題，Timsort 設定了臨時記憶體。它将兩個 run 中較小的（同時調用 runA 和 runB）放在這個臨時記憶體中。
GALLOPING（飛奔模式）
當 Timsort 歸并 A 和 B 時，它注意到一個 run 已經連續多次「獲勝」。如果 run A 的數值完全小于 run B，那麼 run A 會回到原始位置。歸并這兩個 run 會耗費巨大工作量，而且還不會取得任何效果。
通常情況下，資料會有一些預設的内部結構。Timsort 假設，如果 run A 中的值大多低于 run B 的值，那麼 A 的值可能就會小于 B。
然後 Timsort 将進入飛奔模式。Timsort 不是檢查 A[0] 和 B[0]，而是二分法搜尋 B[0] 在 A[0] 中的合理位置。這樣，Timsort 可以将 A 的整個部分移動到合适的位置。然後，Timsort 在 B 中搜尋 A[0] 的适當位置。然後，Timsort 将立即移動整個 B 到合适的位置。
Timsort 檢查 B[0]（值為 5），并使用二分法搜尋查找其 A 中的正确位置。
現在 B[0] 在 A 清單的後面，Timsort 檢查 B 的正确位置是否有 A[0]（即 1），是以我們要看 1 的位置。這個數在 B 的前部，現在我們知道 B 在 A 的後邊，A 在 B 的前邊。
如果 B[0] 的位置非常接近 A 的前端（反之亦然），那麼這個操作就沒必要了。Timsort 也會注意到這一點，并通過增加連續獲得 A 或 B 的數量提高進入飛奔模式的門檻。如果飛奔模式合理，Timsort 使它更容易重新進入該模式。
簡而言之，Timsort 做了兩件非常好的事情：
- 具有預設的内部結構的數組具有良好的性能
- 能夠保持穩定的排序
在此之前，為了實作穩定的排序，必須将清單中的項壓縮為整數，并将其排序為元組數組。
代碼
下面的源代碼基于我和 Nanda Javarma 的工作。源代碼并不完整，也不是類似于 Python 的官方 sort() 源代碼。這隻是我實作的一個簡化的 Timsort，可以對 Timsort 有個整體把握。此外，Python 中的内置 Timsort 算法是在 C 中正式實作的，是以能獲得更好的性能。
Timsort 的原始源代碼：https://github.com/python/cpython/blob/master/Objects/listobject.c。
# based off of this code https://gist.github.com/nandajavarma/a3a6b62f34e74ec4c31674934327bbd3
# Brandon Skerritt
# https://skerritt.tech
def binary_search(the_array, item, start, end):
if start == end:
if the_array[start] > item:
return start
else:
return start + 1
if start > end:
return start
mid = round((start + end)/ 2)
if the_array[mid] < item:
return binary_search(the_array, item, mid + 1, end)
elif the_array[mid] > item:
return binary_search(the_array, item, start, mid - 1)
else:
return mid
"""
Insertion sort that timsort uses if the array size is small or if
the size of the "run" is small
"""
def insertion_sort(the_array):
l = len(the_array)
for index in range(1, l):
value = the_array[index]
pos = binary_search(the_array, value, 0, index - 1)
the_array = the_array[:pos] + [value] + the_array[pos:index] + the_array[index+1:]
return the_array
def merge(left, right):
"""Takes two sorted lists and returns a single sorted list by comparing the
elements one at a time.
[1, 2, 3, 4, 5, 6]
"""
if not left:
return right
if not right:
return left
if left[0] < right[0]:
return [left[0]] + merge(left[1:], right)
return [right[0]] + merge(left, right[1:])
def timsort(the_array):
runs, sorted_runs = [], []
length = len(the_array)
new_run = [the_array[0]]
# for every i in the range of 1 to length of array
for i in range(1, length):
# if i is at the end of the list
if i == length - 1:
new_run.append(the_array[i])
runs.append(new_run)
break
# if the i'th element of the array is less than the one before it
if the_array[i] < the_array[i-1]:
# if new_run is set to None (NULL)
if not new_run:
runs.append([the_array[i]])
new_run.append(the_array[i])
else:
runs.append(new_run)
new_run = []
# else if its equal to or more than
else:
new_run.append(the_array[i])
# for every item in runs, append it using insertion sort
for item in runs:
sorted_runs.append(insertion_sort(item))
# for every run in sorted_runs, merge them
sorted_array = []
for run in sorted_runs:
sorted_array = merge(sorted_array, run)
print(sorted_array)
timsort([2, 3, 1, 5, 6, 7])
Timsort 實際上在 Python 中已經内建了，是以這段代碼隻充當概念解釋。要使用 Timsort，隻需在 Python 中寫：
list.sort() 或者：
sorted(list) 如果你想掌握 Timsort 的工作方式并對其有所了解，我強烈建議你嘗試自己實作它！
原文釋出時間為：2018-11-26
本文來自雲栖社群合作夥伴“
CDA 資料分析師”，了解相關資訊可以關注“
”。