JS 學資料結構與演算法 (排序篇) — 合併排序法 Merge Sort

合併排序法示意圖

合併排序法 Merge Sort

合併排序法定義

合併演算法與上一篇介紹的快速排序法一樣，都運用了 Devide and Conquer 的概念，基本上分為兩個步驟：分割與整合。首先利用遞迴把原先未排序的陣列平均分割成兩半，直到各邊都只剩下一個元素（上圖紫色方塊），接著排序後再一一整合起來，最後會合併成一個排序後的陣列（上圖綠色區塊）。

分割 （紫色區塊）

1. 把大陣列分一半成為兩個小陣列
2. 把從上一步驟切好的兩個小陣列再各自分一半
3. 重複步驟 2 直到每個小陣列都只剩一個元素

整合 （綠色區塊）

1. 排序兩個只剩一個元素的小陣列並將其合併
2. 把上一步驟排序好的小陣列合併並排序成一個陣列
3. 重複步驟二直到所有小陣列都合併成一個大陣列

讀者比較有疑問的也許會是這個部分：

Q: [2,3,7,16] 跟 [4,9,11,24] 這兩個陣列是如何合併成最終的已排序陣列呢？

A: 因為這兩個陣列在合併前就已經各自完成排序了，因此只要比較各自最左邊的元素的大小，將比較小的元素放進新陣列中，最後就能完成排序囉！其實從一開始只有一個元素要進行合併時就是運用這個方法喔（只有一個元素的陣列視為已排序）！

時間複雜度

最佳：O(n log n)
最差：O(n log n)
平均：O(n log n)

時間複雜度的部分，我們依然可以分為 “分割” 與 “整合” 兩個步驟來看。

分割：分割含有 n 個元素的陣列需要 (n-1) 次步驟。

合併：若要合併的兩陣列共用 n 個元素，每次排序與合併必須經過 n 次步驟。

如圖所示，總共4個元素的小陣列，因為每次都是比較最左邊的元素，將較小的一項加到新陣列中，因此總共需要 4 個步驟。

接著要考量的是需要經過幾個回合的合併，從上圖的例子可以發現，原先 8 個獨立的元素經過一次合併後變成 4 個小陣列，再經過一次合併後成為兩個陣列，最後兩個陣列再合併形成最終排序過後的一個陣列，如此每次合併都讓下回需要合併的陣列數減少一半，這表示總共需要合併的回合數會是以 2 為底的 log n 次。

因此合併排序法的時間複雜度為：

時間複雜度 = 分割步驟數 + 合併步驟數 = 分割步驟數 + 每回合合併所花步驟數 * 回合總數 = (n-1) + log n * n

而由於時間複雜度只看最高項係數且忽略常數，因此得出的時間複雜度為 O(n log n)。

程式碼範例

const numbers = [27, 34,16, 4, 1, 5, 69, 65, 223, 7, 0];
function mergeSort (array) {
  if (array.length === 1) {
    return array;
  };
  const length = array.length;
  const middle = Math.floor(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 leftIndex = 0;
  let rightIndex = 0;
  while(leftIndex < left.length && rightIndex < right.length){
    if(left[leftIndex] < right[rightIndex]){
      result.push(left[leftIndex]);
      leftIndex++;
    } else{
      result.push(right[rightIndex]);
      rightIndex++;
    }
}
return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}
const answer = mergeSort(numbers);

完整程式碼連結

合併排序法一樣使用了遞迴的概念，一開始看也許會沒有那麼直覺，而整個演算法的流程如果跟著本篇文章的內容走的話，要了解程式碼應該不會有太大的問題，就留給讀者自行吸收領會了。

下回預告： 氣泡排序法 （Bubble Sort）