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);

完整程式碼連結

結語

合併排序法一樣使用了遞迴的概念，一開始看也許會沒有那麼直覺，而整個演算法的流程如果跟著本篇文章的內容走的話，要了解程式碼應該不會有太大的問題，就留給讀者自行吸收領會了。如果你對這個系列有興趣，也想跟我一起透過 JavaScript 強化自己對於資料結構與演算法的基礎，歡迎訂閱我，如果覺得這篇文章對你有幫助，也不要吝嗇幫我拍拍手吧！

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

JS 學資料結構與演算法JS 學資料結構與演算法全系列：

(1) 快速排序法 Quick Sort 

(2) 合併排序法 Merge Sort (本篇)

(3) 氣泡排序法 Bubble Sort

(4) 選擇排序法 & 插入排序法

「好文轉自莫力全 Kyle Mo–JS 學資料結構與演算法 (排序篇) — 合併排序法 Merge Sort，如果你喜歡他的文章歡迎回到他的部落格看更多:)」

希望以上能幫助到你藉由JS 更了解資料結構與演算法。如果想要對JavaScript本身有更多的瞭解，Udemy這裡開課囉！老師從基礎手把手的帶你實作，教你主流寫法提升 JS 開發能力！

現在開始上課！

如果你的入門還在單打獨鬥，歡迎來到快樂學程式找到志同道合的夥伴，你的自學之路不孤單。

快樂學程式