合併排序法教學：原理、程式碼與時間複雜度

用白話說明原理

含零個或一個元素的串列本來就是已排序的。對較長的串列：

1. 分割：把串列分成左半與右半。
2. 征服：用合併排序分別排序每一半。
3. 合併：合併兩個已排序的半邊。比較兩邊最前面的元素，把較小的移到輸出，重複直到其中一邊空了；然後把另一邊剩下的複製過去。

所有真正的工作都發生在合併步驟，合併兩個總長度為 n 的已排序串列，最多只需要 n − 1 次比較。

逐步範例

將 [38, 27, 43, 3, 9, 82, 10] 排序。

最後一次合併比較兩邊的最前端：27 與 3 取 3，27 與 9 取 9，27 與 10 取 10，27 與 82 取 27，38 與 82 取 38，43 與 82 取 43，最後再複製 82。七個元素共六次比較。

Python 實作

def merge(left, right):
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:     # <= takes from left on ties: stable
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    out.extend(left[i:])            # one of these is empty
    out.extend(right[j:])
    return out
def merge_sort(items):
    """Return a new sorted list."""
    if len(items) <= 1:
        return list(items)
    mid = len(items) // 2
    return merge(merge_sort(items[:mid]), merge_sort(items[mid:]))
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))   # [3, 9, 10, 27, 38, 43, 82]
print(merge_sort([]))                           # []

這個由上而下的版本很清楚，但會複製切片。由下而上的版本則完全避開遞迴：先合併寬度為 1 的段落，再合併寬度 2、4，依此類推。

def merge_sort_bottom_up(items):
    a = list(items)
    width = 1
    while width < len(a):
        for lo in range(0, len(a), 2 * width):
            mid, hi = lo + width, lo + 2 * width
            a[lo:hi] = merge(a[lo:mid], a[mid:hi])
        width *= 2
    return a

由下而上的版本重複使用上面的 merge。標準函式庫也有 heapq.merge，可以惰性地合併任意數量的已排序可迭代物件。

時間與空間複雜度

遞迴式為 T(n) = 2T(n/2) + O(n)。遞迴樹的每一層總共做 O(n) 的工作，約有 log₂ n 層，所以總計是 O(n log n)。對一百萬筆資料來說，大約是 20 層。

合併排序與其他排序法的比較

合併排序是穩定的，因為兩個元素相等時，合併會先取左半的元素，所以相等的元素保持原順序。與快速排序相比，它保證最差情況為 O(n log n)，但需要 O(n) 的額外記憶體，而且在陣列上通常要搬動更多資料。與堆積排序相比，它是穩定的，並且依序存取記憶體，對快取與磁碟都很友善。

變體與常見錯誤

• 自然合併排序（natural merge sort）會偵測已經排序好的順串並加以合併，對已排序的輸入可達 O(n)。Timsort 是改良過的自然合併排序，對短的順串使用二分插入排序。
• 對小的子串列（例如少於約 10 到 30 個元素）改用插入排序，以降低開銷。
• 在鏈結串列上，合併排序不需要額外緩衝區：合併只需重新連接節點，因此它通常是排序鏈結串列的首選。
• 外部合併排序先排序能放進記憶體的區塊，寫入磁碟，再進行 k 路合併。資料庫與 GNU sort 之類的工具，都用這個概念處理大型檔案。
• 計算逆序對：合併時，每當從右半取出一個元素，它就比左半所有剩餘的元素都小。

何時使用合併排序

需要穩定排序且保證 O(n log n) 時間、排序鏈結串列，或資料大到記憶體放不下時，請選擇合併排序。在 Python 中，直接呼叫 sorted() 或 list.sort() 即可：它們實作的是 Timsort，也就是合併排序的變體，所以你已經擁有這些特性。親手寫合併排序是經典的面試題，常延伸到計算逆序對或合併 k 個已排序的串列。