TimSort - Python 內建排序法

Posted on 2024-03-24

TimSort 是 Python 內建的排序法，是一種混合排序法，結合了 Merge Sort 和 Insertion Sort 的特性，並且會根據資料的特性自動切換這兩種排序法。

TimSort 一開始是 Peter McIlroy
在他的論文 Optimistic Sorting and Information Theoretic Complexity 中提出的。
接著在 2002 年由 Tim Peters 為 Python 2.3 開發出來，主要是為了解決當時 Python 內建的排序法 QuickSort 的問題。

目前依舊被廣泛應用於各種程式語言和軟體中，例如 Python、Java、Android、V8 等。

歷史背景

TimSort 當初被 Tim Peters 選中進而實作出來是因為當時 Python 2.2 以前採用的 QuickSort 引發的以下幾個問題：

QuickSort 是一個不穩定的排序法，這意味著排序後相同的元素的相對位置可能會改變。
這在實際應用場景中會是個災難，在一些現實情況是必須允許有相同的元素存在，但是又必須保持他們的相對位置不變。例如排序時，如果資料之間擁有相同的 key，那麼排序後的結果就會變得不可預測。
理論科學家通常並不是很在意時間複雜度 O 記號的常數項，但在實際應用中這些常數項往往就是影響效能的關鍵。
QuickSort 在面對快要排序好的資料時，效能表現會變得很差，最壞情況下的時間複雜度是 O(n^2)，而這樣的資料在實際應用中是很常見的。
理論測試資料往往是隨機的，但這在實際應用中並不是很常見，實際應用中的資料往往有一定的規律性，這就會導致理論科學家測試的結果和實際應用的效能表現有很大的差異。
而實際應用場景才是 Tim Peters 在意的。

TimSort

TimSort 的核心思想是將資料分成多個小塊，然後對這些小塊使用 Insertion Sort 進行排序，最後再將這些小塊使用 Merge Sort 合併成一個大塊。

這樣的好處是：

因材施教：Insertion Sort 在面對小塊資料時效能表現出色，而 Merge Sort 在面對處理大規模數據時效率更高。TimSort
巧妙地結合了這兩種算法，根據數據的特性自動切換，發揮它們各自的長處。
保證效率：無論在最佳、平均還是最壞情況下，TimSort 的時間複雜度都能保證在 O(n log n) 的範圍內。這使得它成為一種高效且可靠的排序算法。
穩定性：TimSort 是一種穩定的排序算法，這意味著相等元素的相對位置在排序前後不會改變。這一特性在某些應用場景中非常重要。
適應性：TimSort 能夠根據數據的分佈特點自動調整策略。當面對部分已經排序的數據時，它能夠充分利用數據的有序性，從而獲得更好的性能表現。

基本上，演算法可以分成以下幾個部分：

分割數據：將數據分割成多個小塊，每個小塊的大小為 minrun，通常取 32 或 64。
插入排序：對每個小塊應用插入排序，使其成為一個有序的小塊。
合併排序：使用合併排序將這些有序的小塊逐步合併，直到整個數據集完全有序。
重複合併：重複步驟 3，直到所有的小塊都合併成一個完整的有序數據集。

那演算法的實現細節可以參考 Python doc。

Python 範例

以下是一個 Python 實現的 TimSort 範例，需要注意的是，這只是一個簡單的實現，實際上 Python 內建的 TimSort 是使用 C
語言實現的，效率更高。

def insertion_sort(arr, left, right):
    for i in range(left + 1, right + 1):
        key = arr[i]
        j = i - 1
        while j >= left and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key


def merge(arr, left, mid, right):
    left_arr = arr[left:mid + 1]
    right_arr = arr[mid + 1:right + 1]
    i = j = 0
    k = left

    while i < len(left_arr) and j < len(right_arr):
        if left_arr[i] <= right_arr[j]:
            arr[k] = left_arr[i]
            i += 1
        else:
            arr[k] = right_arr[j]
            j += 1
        k += 1

    while i < len(left_arr):
        arr[k] = left_arr[i]
        i += 1
        k += 1

    while j < len(right_arr):
        arr[k] = right_arr[j]
        j += 1
        k += 1


def timsort(arr):
    min_run = 64
    n = len(arr)

    for i in range(0, n, min_run):
        insertion_sort(arr, i, min(i + min_run - 1, n - 1))

    size = min_run
    while size < n:
        for start in range(0, n, size * 2):
            mid = start + size - 1
            end = min(start + size * 2 - 1, n - 1)
            merge(arr, start, mid, end)
        size *= 2

    return arr


if __name__ == '__main__':
    data = [5, 1, 4, 2, 8, 0, 2]
    print(timsort(data))  # [0, 1, 2, 2, 4, 5, 8]

    import random

    data = random.sample(range(1000), 1000)
    print(data)
    print(timsort(data))

TimSort - Python 內建排序法

歷史背景

TimSort

Python 範例

參考資料

相關文章