🧩 合併排序法 (Merge Sort) 核心概念

合併排序法同樣是「分而治之」(Divide and Conquer) 策略的經典代表。它的運作哲學是：與其一次處理一大堆雜亂的數字，不如把它們一直切半，直到每個區塊都只有一個數字（一個數字自然算排好序了），然後再兩兩合併起來。

🎯 兩步核心流程

  1. 分割 (Divide)： 將陣列從中間對半切，不斷遞迴切分，直到每個子陣列只剩 1 個元素。
  2. 合併 (Merge)： 將相鄰的兩個子陣列，由左至右依序比較大小，挑選較小的元素放入新的陣列中，直到合併成一個完整的已排序陣列。

⏱️ 效能與複雜度

  • 時間複雜度： 永遠都是 O(n log n)。不論資料多亂或多整齊，效能極度穩定！
  • 空間複雜度： O(n)。這是它的致命傷，合併時需要額外借用一個與原陣列一樣大的空間來存放資料。
  • 穩定性： 穩定。數值相同的元素在排序後不會改變原本的相對位置。

💡 為什麼要用合併排序？

當你極度需要「穩定的執行時間」且「不怕消耗額外記憶體」時，它就是首選。此外，因為它是循序存取資料，非常適合用來排序「連結串列 (Linked List)」或是資料大到無法全部塞進記憶體的「外部排序 (External Sorting)」。

合併排序法 (Merge Sort)

回首頁

點擊「開始排序」觀察過程