昨天學習了遞迴 (Rcursion)，今天來學習可以用遞迴實作的合併排序 (Merge Sort)。

基本概念

合併排序法會有以下步驟：

1. 分割： 把陣列對半切，遞迴分割直到每段只剩 1 個元素。
2. 排序子陣列： 每個小陣列本身只有 1 個元素，所以已排序好。
3. 合併： 用雙指標比較兩個已排序子陣列，把較小者依序放入新陣列。
4. 重複合併： 一路往上合併，直到整個陣列合併完成。

假設我們現在有一串資料需要排序 [5, 2, 1, 7, 8, 3, 9, 6]

我們會需要先把它分解：

1. 資料切一半成 [5, 2, 1, 7]、[8, 3, 9, 6]
2. 兩邊都各再切一半 [5, 2]、[1, 7]、[8, 3]、[9, 6]
3. 四個區塊都各再切一半 [5]、[2]、[1]、[7]、[8]、[3]、[9]、[6]

結果:[5]、[2]、[1]、[7]、[8]、[3]、[9]、[6]

再來就要把他們全部合併起來

第一步：兩兩合併 (小的排前面)

• [5] + [2] → [2, 5]
• [1] + [7] → [1, 7]
• [8] + [3] → [3, 8]
• [9] + [6] → [6, 9]

結果：[2, 5]、[1, 7]、[3, 8]、[6, 9]

第二步：再往上合併 (小的先加到陣列)

• [2, 5] + [1, 7] →

  • 2 vs 1 → [1]
    • 原陣列： [2, 5] + [7]
    • 新陣列： [1]
  • 2 vs 7 → [1, 2]
    • 原陣列： [5] + [7]
    • 新陣列： [1, 2]
  • 5 vs 7 → [1, 2, 5]
    • 原陣列： [] + [7]
    • 新陣列： [1, 2, 5]
  • 剩下 7 → [1, 2, 5, 7]

• [3, 8] + [6, 9] →

  • 3 vs 6 → [3]
    • 原陣列： [8] + [6, 9]
    • 新陣列： [3]
  • 8 vs 6 → [3, 6]
    • 原陣列： [8] + [9]
    • 新陣列： [3, 6]
  • 8 vs 9 → [3, 6, 8]
    • 原陣列： [] + [9]
    • 新陣列： [3, 6, 8]
  • 剩下 9 → [3, 6, 8, 9]

結果：[1, 2, 5, 7]、[3, 6, 8, 9]

第三步：最終合併

[1, 2, 5, 7] + [3, 6, 8, 9] →

• 1 vs 3 → 1
  • 原陣列： [2, 5, 7] + [3, 6, 8, 9]
  • 新陣列： [1]
• 2 vs 3 → 2
  • 原陣列： [5, 7] + [3, 6, 8, 9]
  • 新陣列： [1, 2]
• 5 vs 3 → 3
  • 原陣列： [5, 7] + [3, 6, 8, 9]
  • 新陣列： [1, 2, 3]
• 5 vs 6 → 5
  • 原陣列： [7] + [6, 8, 9]
  • 新陣列： [1, 2, 3, 5]
• 7 vs 6 → 6
  • 原陣列： [7] + [8, 9]
  • 新陣列： [1, 2, 3, 5, 6]
• 7 vs 8 → 7
  • 原陣列： [] + [8, 9]
  • 新陣列： [1, 2, 3, 5, 6, 7]
• 剩下 8,9 → [1, 2, 3, 5, 6, 7, 8, 9]

結果：[1, 2, 3, 5, 6, 7, 8, 9] (完成排序!)

參考程式碼

def merge(left, right):
    
    # 要加入的新陣列
    merged = []
    
    # index
    i = 0
    j = 0
    
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:     # 保持穩定排序
            merged.append(left[i])
            i += 1                  # 換下一筆
        else:
            merged.append(right[j])
            j += 1                  # 換下一筆

    # 將剩下的加入
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged

def merge_sort(array):

    # 遞迴進行合併排序
    if len(array) <= 1:  # 切到最小長度 1
        return array
    
    mid = len(array) // 2             # 取整數，如果長度是 7，就會切成 3、4
    left = merge_sort(array[:mid])    # 左半排序 (遞迴)
    right = merge_sort(array[mid:])   # 右半排序 (遞迴)

    return merge(left, right)       # 合併


data = [5, 2, 1, 7, 8, 3, 9, 6]
print(merge_sort(data))

謝謝!

參考資料
增井敏克，《圖解演算法原理》，碁峰資訊，2023 年
ChatGPT