前言

昨天的 Insertion Sort 是一個成本取決於輸入資料形狀的排序演算法，資料越接近已排序狀態，它花費的成本就越少。可是實務上不一定知道資料長什麼樣，從外部 API 回來的陣列、使用者自己上傳的檔案，裡面有多少順序相反的配對事先無從得知，這時如果還是拿 Insertion Sort 去排序，就要做好它退到 O(N²) 的準備。那有沒有一種排序，不管拿到什麼輸入，成本都差不多呢？

先來看看前三個排序的共同點。Bubble Sort 交換相鄰的兩格、Selection Sort 每輪把最小值換到前面、Insertion Sort 把一個元素往左送到定位，做法各有不同，但它們都在同一個陣列裡挪動元素，而且一步只能讓一個元素往正確的方向前進。那有沒有另一個角度的解法呢？

Day 13 介紹遞迴時說過，有些問題是由「形狀相同、規模更小」的子問題一層層組成的，而排序其實也是，要把一個陣列排好，可以先拆成兩半來做，先把左半邊排好，再把右半邊排好，兩半各自排好後，再想辦法合併成一個完整排好的陣列，而這個合併的辦法就是今天要介紹的 Merge Sort～

Merge Sort：對半拆開，再合併回來

Merge Sort 一句話定義如下：

Merge Sort（合併排序）不斷把陣列對半拆開，直到每個子陣列只剩一個元素，再把這些已排序的子陣列逐層合併回一個完整排好的陣列。

這個拆開又合併的做法有個名字，叫做分而治之 (Divide and Conquer)：

分而治之 (Divide and Conquer) 是把一個問題拆成幾個規模更小、形狀相同的子問題，各自解完之後，再把子問題的答案組合回原問題的答案。

分而治之的名字就是它的前兩個步驟：拆開（divide）、解掉子問題（conquer），最後再把子問題的答案組合起來（combine）。Merge Sort 的 divide 是對半拆、conquer 是遞迴排序兩半，combine 則是把兩段結果合併（merge），而最後這一步正是它名字的由來。

Merge Sort 的通用步驟

Merge Sort 每次處理一段陣列，可以拆成四步：

1. 如果這段陣列只剩 1 個元素或是空的，它本來就是排好的，直接回傳
2. 否則算出中間的位置，把這段陣列切成左右兩段
3. 對左右兩段各自從第 1 步再做一次，直到兩段都排好
4. 把兩段已排序的結果合併成一段，然後回傳

和前兩篇的步驟有個地方不同，這裡的第 3 步指回自己，因此同一套步驟會往下作用在越來越小的兩段上。

Divide：拆到單一元素

拆分是這幾步裡最單純的，只要算出中間的位置，把陣列切成兩段就好。沿用 Day 14 那個亂序陣列 [6, 5, 3, 1, 8, 7, 2, 4] 來看看拆的過程。8 個元素的中間位置是 index 4，於是切成 [6, 5, 3, 1] 和 [8, 7, 2, 4]，這兩段再各自對半切，一路切下去。

圖 1 [6, 5, 3, 1, 8, 7, 2, 4] 對半切 3 次就拆到單一元素

8 個元素對半切 3 次，每一段就只剩 1 個元素，而切出來的 8 段之間仍保持原本的左右順序，[6] 在最左邊、[4] 在最右邊，只是它們現在各自獨立。

另外，長度是奇數的時候兩半不會一樣長，Math.floor 會讓左邊少一格，例如 7 個元素會切成 3 和 4，接著一樣繼續往下切到只剩單一元素。

Conquer：排序子問題

拆完之後，conquer 這一步要做什麼呢？

先看看拆的過程實際做了哪些事：算中間的 index、把陣列切成兩段，然後對兩段重複同一件事。這裡面沒有任何一次比較，也沒有任何一個元素改變位置，拆的過程裡完全沒有排序發生。那排序是在哪裡發生的？答案是在合併時發生，而 conquer 這一步做的就是遞迴呼叫本身，把左半邊和右半邊各自交給 Merge Sort 再排一次。

遞迴要停下來需要 base case，Merge Sort 的 base case 就是拆到底的那個狀態，因為一個元素不可能和誰順序顛倒，本來就能視為已排序，所以長度 1 的陣列直接回傳即可。也就是說，對半拆到單一元素，就是把排序這個問題縮到一個不必動手就成立的狀態。

那如果傳進來的是空陣列呢？base case 如果只認「長度剛好等於 1」，空陣列就不符合，於是繼續往下拆，而它對半切出來的兩半也都是空陣列，一路碰不到 base case。這正是 Day 13 說的第二種寫錯方式，base case 明明存在，縮小問題的方式卻抵達不了它，最後同樣是 stack overflow。因此條件要放寬成「長度小於或等於 1」才對。

Merge：兩個有序陣列如何合併

現在有兩段各自排好的陣列，要把它們合併成一段排好的，會怎麼做呢？直覺想法是接在一起後再排一次，但這樣等於把問題原封不動退回去，前面都白做了，合併必須比「重新排一次」的成本低，Merge Sort 才有意義。

這個成本差的來源是那兩段已經排好的條件。既然兩段各自由小到大，整份資料裡最小的元素就只可能出現在兩個地方：左邊那段的最前面，或右邊那段的最前面。所以每一步只需要比較這兩個，把小的那個取走，取走之後被取走的那一邊往後遞補一格，重複同一件事直到其中一邊空掉。這做法稱為雙指標：

雙指標 (Two Pointers) 是在兩個序列上各放一個索引，每次只比較兩個索引指到的元素，取走一個之後只把那一邊的索引往前移。

昨天把 Insertion Sort 比喻為整理撲克牌，合併其實也可以用撲克牌來比喻：桌上有兩疊已經由小到大排好的牌，要把它們併成一疊，只要每次翻開兩疊最上面那張、把比較小的抽走放進新的一疊，就能一路併完，不需要去看牌堆底下有什麼。

圖 2 兩疊排好的牌併成一疊，每次只看得到兩疊最上面那張

這個雙指標做法看起來很熟悉，因為 Day 09 我們就用過了。當時把兩條稀疏向量相加，就是各派一個 cursor 從頭往前走，比較兩邊目前停在第幾維，維度小的那個先前進，而先走完的那一條結束之後，另一條剩下的項整批接到結果後面。Merge 這裡的兩個索引做的是同一件事，只有兩個地方不一樣：稀疏向量存在 Linked List 上，只能靠 cursor 一格一格往前，而這裡是陣列，位置可以直接用數字表示；另外兩邊相等的時候，稀疏向量是把兩個值加起來、兩個 cursor 一起前進，合併則是只取一邊，也只動那一邊。

試跑一次執行流程

拆分的部分圖 1 已經走完，接下來從最底層那 8 段開始，看合併怎麼一層一層做回來。

圖 3 合併的全貌，每一列的分組都不同，但要處理的元素總數都是 8 個

第一層：8 段兩兩合併成 4 段

最底層的每一段都只有 1 個元素，兩邊各只有一個能比，所以每次合併都只比 1 次：

1. [6] 和 [5]：比較 6 和 5，5 比較小先取走，左邊剩下的 [6] 整段接上，得到 [5, 6]
2. [3] 和 [1]：比較 3 和 1，取走 1，再接上 [3]，得到 [1, 3]
3. [8] 和 [7]：比較 8 和 7，取走 7，再接上 [8]，得到 [7, 8]
4. [2] 和 [4]：比較 2 和 4，這次是左邊比較小，取走 2，再接上 [4]，得到 [2, 4]

這一層做了 4 次合併、總共 4 次比較，8 段變成 4 段，而且每一段裡面都排好了。

第二層：4 段合併成 2 段

這一層每邊有 2 個元素，索引開始會往前移：

1. [5, 6] 和 [1, 3]：比較 5 和 1，取走 1；右邊遞補成 3，比較 5 和 3，取走 3。這時右邊空了，左邊剩下的 [5, 6] 整段接上，得到 [1, 3, 5, 6]
2. [7, 8] 和 [2, 4]：比較 7 和 2，取走 2；比較 7 和 4，取走 4。右邊又空了，接上 [7, 8]，得到 [2, 4, 7, 8]

這一層各花 2 次比較、合計 4 次。得到的兩段各有 4 個元素，正是原本陣列的左右兩半排好之後的樣子。

第三層：2 段合併成完整結果

最後一次合併，左邊是 [1, 3, 5, 6]、右邊是 [2, 4, 7, 8]：

1. 比較 1 和 2，取走 1，結果是 [1]
2. 比較 3 和 2，取走 2，結果是 [1, 2]
3. 比較 3 和 4，取走 3，結果是 [1, 2, 3]
4. 比較 5 和 4，取走 4，結果是 [1, 2, 3, 4]
5. 比較 5 和 7，取走 5，結果是 [1, 2, 3, 4, 5]
6. 比較 6 和 7，取走 6，結果是 [1, 2, 3, 4, 5, 6]

走完第 6 步，左邊那段已經全部被取走，右邊還剩 [7, 8]。這時候不必再比較了，右邊剩下的本來就由小到大，而且每一個都比已經取走的元素大，直接整段接在後面就是 [1, 2, 3, 4, 5, 6, 7, 8]，排序完成。

因此 8 個元素的合併只花了 6 次比較，比元素總數還少。合併兩段長度加起來是 N 的陣列，比較次數最多是 N - 1 次，也就是每比一次就取走一個、最後剩一個不必比；最少則是比較短那一段的長度，也就是短的那一邊很早就空掉，長的那一邊整段接上。

圖 4 每一步只比較兩段最前面那一個，只有被取走的那一邊往前移

寫成程式

Merge Sort 寫成程式如下：

function mergeSort(array) {
  if (array.length <= 1) {
    return array; // 長度 0 或 1 的陣列本來就是排好的
  }

  const middle = Math.floor(array.length / 2);
  const left = array.slice(0, middle);
  const right = array.slice(middle);

  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  const result = [];
  let i = 0; // 指向 left 還沒被取走的最前面那一格
  let j = 0; // 指向 right 還沒被取走的最前面那一格

  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i]);
      i++;
    } else {
      result.push(right[j]);
      j++;
    }
  }

  // 其中一邊已經空了，另一邊剩下的本來就排好，直接整段接上
  return result.concat(left.slice(i), right.slice(j));
}

和前兩篇不同的是，這裡不需先複製一份 [...array]，因為 slice 每次都回傳新的陣列，merge 也是把結果推進新的 result，呼叫端傳進來的那個陣列從頭到尾沒有被動到，因此 Merge Sort 不是原地排序。

實際的執行順序：拆和合併是交錯的

圖 1 那種逐層的畫法，加上剛剛一層一層走的試跑流程，很容易讓人以為 Merge Sort 是先把整個陣列拆到底，再一層一層合併回來，但其實不是。

關鍵在 return merge(mergeSort(left), mergeSort(right)) 這裡，要呼叫 merge，得先算出兩個參數，而 mergeSort(left) 在前面，所以左半邊會整個排完，右半邊才開始拆。把每一次拆和每一次合，按實際發生的順序標出來，如下面的示意圖。

圖 5 拆和合併實際發生的順序

[8, 7, 2, 4] 在第 8 步才被切開，而 [1, 3, 5, 6] 早在第 7 步就排好了，所以同一時間不會有 8 段子陣列全部攤在那。Day 13 說過遞迴的額外空間通常就是它的最大遞迴深度，這裡就能看到，掛在 call stack 上的 frame 只有從最上層往下的一條路徑，深度就是拆分的層數。

時間與空間複雜度

接著來看看時間與空間複雜度～

時間複雜度：為什麼是 O(N log N)？

Merge Sort 是目前遇到第一個時間複雜度為 O(N log N) 的演算法，它的成本來自兩個部分。

第一個部分是層數，每次對半切，8 變 4、4 變 2、2 變 1，切 3 次就到底，合併也就進行 3 層。而這裡的「切 3 次」，換個問法就是「8 要連續除以 2 幾次才會剩下 1」，這個問題的答案有個名字，叫做以 2 為底的對數，寫成 log₂ 8 = 3。從指數的方向看就是 2³ = 8，所以 8 要砍半 3 次才會到 1，對數就是指數的反運算。一般式因此是 log₂N，而 Big O 會省略對數的底數，寫成 O(log N)。

換句話說，資料量每加倍才多一層。這個成長方式慢到什麼程度呢？1,024 個元素只有 10 層，而資料量再往上翻近一千倍、到一百萬筆，層數也只從 10 變成 20。

第二個部分是每一層的工作量，同一層雖然有好幾段子陣列，但它們合起來就是原本那個陣列，一個元素都沒多、也沒少，每一層要處理的元素總數固定就是 N。最底層是 4 次合併、每次 2 個元素；中間層是 2 次合併、每次 4 個；最頂層是 1 次合併、8 個，三層加起來都是 8。越往上合併的次數越少，但每次要處理的越多，兩者剛好抵銷。

把剛剛試跑的三層數字整理如下：

比較次數比元素總數少，因為其中一邊先空掉後，另一邊剩下的整段接上，不必再比。從圖 3 也可看出，每一列的格子分組都不同，但每一列的格子總數都是 8 格。所以總工作量是「每層 N」乘上「log N 層」，也就是 O(N log N)。

這裡和 Day 06 的 Binary Search 有個差別。Binary Search 每比較一次就丟掉一半，它只往下走一條路，總共 O(log N) 步就結束；Merge Sort 對半切之後兩邊都要繼續處理，沒有任何一半被丟掉，所以每一層都得走過全部 N 個元素。也就是說，log N 來自「切幾次」，N 來自「每一層都要全部走過一遍」，兩者相乘才是 Merge Sort 的成本，對半切不會讓工作量減半。

為何對半切一定要切在中間

對半切不會讓工作量減半，這也是對半切一定要切在中間的原因。假設每次不切中間，而是切成 1 個和 N - 1 個，程式一樣跑得出正確答案，但每切一次只讓問題少 1 個元素，8 個元素的層數就從 3 層變成 7 層。層數一旦從 log N 變成和 N 同一個量級，「每層 N」乘上去就是 N² 了。實際拿完全反序的 8 個元素去跑，對半切要 12 次比較，切成 1 和 7 要 28 次，剛好就是 N(N-1)/2。

這個切法退化成什麼呢？每一層合併都變成「把 1 個元素併進一段已排序的陣列」，這正是 Insertion Sort 內層迴圈在做的事。也就是說，Merge Sort 的優勢全部建立在對半切上，切得不平均，它就會往 O(N²) 靠回去。

O(N log N) 和 O(N²)

O(N log N) 和前三個排序的 O(N²) 差多少呢？把兩種成長方式的比較次數估計值放在一起：

N 等於 8 的時候兩邊只差 1.2 倍，這也是為什麼同一個陣列 Day 14 花 28 次比較、今天花 14 次，看起來好像還好，但資料量變大後情況就不太一樣了，一百萬筆的時候一邊是五千億次、一邊是兩千萬次，差了兩萬五千倍。也就是說，資料少時選哪個都無所謂，資料多時這個選擇會決定程式跑不跑得完。

成本不隨輸入改變

昨天用四種輸入比較過三個排序的比較次數，把 Merge Sort 加進來看看～

Insertion Sort 那一欄從 7 跑到 28，跨了四倍；Merge Sort 那一欄只在 12 和 14 之間。而如果把每一層的數字拆開來看，四種輸入的最底層都是 4 次、中間層都是 4 次，差異落在最頂層那次合併，4 次或 6 次而已。完全排好和完全反序都落在 12，原因是這兩種輸入下每一次合併都有一邊的元素全部小於另一邊，所以總會有一邊先空掉、剩下的整段接上，比較次數剛好踩在下限。

為什麼會這麼平呢？因為 Merge Sort 的比較次數只由兩件事決定：切幾次，以及每一層有多少元素。這兩件事都只跟陣列的長度有關，和裡面的值排成什麼樣子無關。用昨天的說法來說，Merge Sort 不是 adaptive 的，資料再整齊，它也照樣把陣列拆到底再合併回來，省不下任何一層。

這張表也可看出，完全排好那一列，Merge Sort 反而比 Insertion Sort 慢，因為 Merge Sort 每一次合併都要配置一個新陣列、每一層都要走過所有元素，這些是固定成本，在資料量小時佔比就很高。昨天提過不少實務上的排序在切到夠小的子陣列時會改用 Insertion Sort，原因也在這裡。

換句話說，Merge Sort 是拿一個上限換掉不確定性。Insertion Sort 的成本取決於輸入夠不夠整齊，整齊時只要 7 次比較，完全反序就要付 O(N²)；Merge Sort 沒有這種落差，它三種情況都是 O(N log N)。

昨天那張表補上 Merge Sort 如下：

空間複雜度：O(N) 的 result 加上 O(log N) 的 call stack

merge 每次都會建立一個新的 result，而最頂層那次合併的 result 長度就是 N，因此 Merge Sort 的 Auxiliary Space 是 O(N)。這是它和前三個排序最明顯的差別，Bubble、Selection、Insertion Sort 都是原地排序 (in-place sort)，額外空間 O(1)。

除了 result 外，還有 call stack，前面那段執行順序看到的是，同一時間掛在 call stack 上的只有一條從最上層往下的路徑，深度就是拆分的層數 log₂N，這部分是 O(log N)。O(N) 的 result 加上 O(log N) 的 call stack，最後寫成 O(N)。

不過 Merge Sort 實際耗掉的其實比 O(N) 還多。每一層的 slice 都會把那一層的元素重新配置一份空間，merge 時又會再配置一份 result，所以整支程式跑完總共配置過的元素數量是 O(N log N)。這些陣列不會同時存在，峰值仍在 O(N)，但配置和回收的次數仍是真實存在的成本。以 8 個元素為例，同一時間活著的最多是一條從根到葉的路徑、8 ＋ 4 ＋ 2 ＋ 1 共 15 格，而整趟跑完配置過的是 48 格。實務上的排序實作會共用一份暫存空間，而不是每次合併都配一份新的，再靠索引範圍表示「現在在排哪一段」。這裡用 slice 是因為拆出來的兩段看得見，比較好對照拆分過程。

Stability：同分的元素會不會被打亂

Merge Sort 還有一個特別的性質，叫做 Stability，先給一句話的定義：

一個排序演算法具備穩定性 (Stability)，是指排序之後鍵值相同的元素之間，仍然保持它們在原本輸入裡的相對順序，而具備這個性質的排序稱為穩定排序 (Stable Sort)。

為什麼要在意 Stability 這特質？以昨天那份評論清單為例，假設清單已經照時間排好，A 最早、H 最新，現在要改成照分數由低到高排序：

const comments = [
  { score: 90, id: 'A' },
  { score: 70, id: 'B' },
  { score: 90, id: 'C' },
  { score: 70, id: 'D' },
  { score: 80, id: 'E' },
  { score: 90, id: 'F' },
  { score: 70, id: 'G' },
  { score: 80, id: 'H' },
];

裡面同分的有三組(90、80、70 各一組)。排完之後，同分的那幾筆還會照時間排好嗎？這決定了「先按時間排，再按分數排」這種兩段式的做法能否成立。如果排序是穩定的，第二次排序只會動到分數的順序，第一次排好的時間順序在同分的那幾組裡會保留下來，兩次排序疊起來就得到「分數低的在前，同分的照時間」；如果不穩定，第二次排序會把第一次的成果洗掉，那就不能分兩次排，要改成一段一次比兩個欄位的比較函式，分數不同時比分數，分數相同時再比時間。兩種做法實務上都有人用，但前者的前提就是排序必須穩定。

把前面那段 merge 拿來排這份清單，比較的條件寫成 left[i].score <= right[j].score，結果是：

70B 70D 70G 80E 80H 90A 90C 90F

三組同分都維持原本的時間順序。接著只改一個字，把 <= 換成 <：

70G 70D 70B 80H 80E 90F 90C 90A

三組同分全部倒過來了。差別在相等時先取哪一邊：left 這一段在原本的陣列裡本來就排在 right 前面，所以相等時取 left，就保留了兩者的相對順序；相等時取 right，等於把後來的那一筆插到前面去，而且每一層合併都會再倒一次。

所以「Merge Sort 是穩定排序」這句話更精確來說是，Merge Sort 穩不穩定取決於 merge 在相等時往哪一邊倒，寫成 <= 才是穩定的。至於不穩定，意思是不保證同分之間的順序，而不是保證會把它們倒過來，這裡的 < 每次都倒，只是因為 merge 的行為本身是確定的。

圖 6 相等時取左邊或取右邊，決定同分元素的相對順序會不會被打亂

小結

小小總結一下今天對 Merge Sort 的認識～

• 為什麼需要 Merge Sort？ 因為前三個排序的成本都由輸入的形狀決定，Insertion Sort 在幾乎排好的資料上只花 7 次比較，拿到完全反序的就要 28 次。可實務上不一定知道資料長什麼樣，這時需要的是一支不管拿到什麼輸入都給同一個上限的排序，而 Merge Sort 的 Best、Average、Worst Case 都是 O(N log N)。
• 用了 Merge Sort 之後差在哪？ 差在拿到了 Worst Case 的保證，也付出了額外空間。前三個排序都是原地排序、額外空間 O(1)，Merge Sort 每次合併都要一個新陣列裝結果，額外空間是 O(N)，再加上遞迴的 call stack 空間 O(log N)。且它不是 adaptive 的，資料再整齊也一樣拆到底再合併，在小陣列上可能比 Insertion Sort 慢。
• Merge Sort 到底是什麼？ 它把陣列對半拆到只剩單一元素，因為單一元素本來就是排好的，再用雙指標把兩段已排序的結果一層層合併回去。排序發生在合併那步，而它的效率來自兩個規律：對半切只會產生 log N 層，而每一層合併總共只處理 N 個元素。

Merge Sort O(N) 的額外空間都花在「合併需要一個新陣列來裝結果」這件事上。那有沒有辦法同樣用分而治之，卻不必準備那個新陣列呢？下一篇的 Quick Sort 就是如此，明天會來介紹～

圖表說明：本文圖表由作者整理，並使用 Claude Code 協助繪製；內容與數據由作者確認。

Reference

• Master the Coding Interview: Data Structures + Algorithms
• 《A Common-Sense Guide to Data Structures and Algorithms, Second Edition》
• Wikipedia：Merge sort
• What is stability in sorting algorithms and why is it important?
• MDN：Array.prototype.slice()
• Sorting Algorithms Animations