今天要介紹的是合併排序法 Merge Sort，合併排序法採用分治法(Divide and Conquer)，它將資料列不斷分割成兩個資料列，這兩個資料列也不斷分割成兩個...持續到所有的資料列都只有一個元素。

接著會開始兩個兩個合併，而且合併的元素會依照大小進行排序，不斷兩兩合併，直到最後就變成一個已經排序好的資料列。

此網頁有小動畫可以參考看看，非常淺顯易懂:
http://notepad.yehyeh.net/Content/Algorithm/Sort/Merge/Merge.php

接著我們來實作吧!完成後會討論其時間複雜度~

1. 首先建立一個 mergeSort(data) 的函式，用於將資料列分開並且最後回傳一個排序好的資料列。
   再建立一個 mergeData(left, right) 的函式，用於將資料列排序並合併。

function mergeSort(data) {
  
}

function mergeData(left, right) {
  
}

console.log(mergeSort([1, 234, -5, 78, -182, 45]));

2. 先完成 mergeSort(data) 的部分，這邊的想法就是取中間值然後將資料列分成兩個子資料列，並且透過函式最後一行的遞迴將資料列分解到只剩一個元素，只要資料列只剩一個元素，就直接回傳該資料列。

3. 因此假如有一個資料列 [1, 2, 3, 4] ，第一次分解會分解成 [1, 2]，[3, 4]，console.log會跳出 split: [1, 2] [3, 4]，進入 mergeData(mergeSort(leftPart), mergeSort(rightPart)) 會變成 mergeData(mergeSort([1, 2]), mergeSort([3, 4]))

4. 此時會再次呼叫 mergeSort(data)一次，分解 mergeSort([1, 2] ，變成 [1] 和 [2] 兩個資料列，它們進入 mergeData(mergeSort(leftPart), mergeSort(rightPart)) 會變成 mergeData(mergeSort([1]), mergeSort([2]))，不過兩個 mergeSort() 的呼叫由於其資料長度不超過2，因此不再繼續遞迴，反倒是傳了兩個陣列給 mergeData()了，變成這樣 mergeData([1], [2])。之後的 [3, 4] 的分解也是同理。

function mergeSort(data) {
  // 假如資料長度小於兩個元素，就可以不用排序了
  if (data.length < 2) {
    return data;
  }

  // 取中間值
  const middle = Math.floor(data.length / 2); // Math.floor() 函式會回傳無條件捨去後的最大整數。

  // 取得分開的左邊資料和右邊資料
  const leftPart = data.slice(0, middle);
  const rightPart = data.slice(middle, data.length);
  console.log('split:', leftPart, rightPart);

  // 透過遞迴不斷將資料做分裂，最後回傳重新合併並排序過的資料列
  return mergeData(mergeSort(leftPart), mergeSort(rightPart));
}

5. 元素傳入 mergeData() 後，我們要把資料排序後合併並回傳。
   由於此兩個資料列都是排序好的狀態或是都只有一個元素，我們可以比較左右兩邊的資料列最前面的值(資料列最小的值)，將比較小的推入 result 空陣列，透過 shift()，較小的值會從資料列移除，直到某邊沒有元素就停止迴圈。

6. 某邊沒有元素就停止迴圈後，另一邊可能還有剩餘的元素，因此再用兩個 while 迴圈做檢查，並把它們推入 result 陣列。最後回傳排序好的 result 陣列。

function mergeData(left, right) {
  // 建立一個可儲存排序後資料的空陣列
  let result = [];

  // 比較左右兩邊的資料列的值
  while(left.length && right.length) {
    if(left[0] <= right[0]) {
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }

  // 有時經過以上的迴圈之後，若某邊資料列的元素先shift完則另一個資料列會有剩下的元素(且是全部資料中的最大值)，將它們推入result陣列
  while (left.length) result.push(left.shift());
  while (right.length) result.push(right.shift());

  console.log('result:', result);
  return result;
}

運行過程如下，可以觀察是怎麼運作的:

2021/02/18 更新: 另一遞迴解法

function mergeSort(arr) {
  if(arr.length === 1) {
    return arr;
  } else {
    const splitIndex = Math.floor(arr.length / 2);
    return merge(mergeSort(arr.slice(0, splitIndex)), mergeSort(arr.slice(splitIndex)))
  }
  
  function merge(arr1, arr2) {
    let merged = [];
    while(arr1.length && arr2.length) {
      if(arr1[0] < arr2[0]) {
        merged.push(arr1.shift());
      } else if(arr1[0] > arr2[0]) {
        merged.push(arr2.shift());
      } else {
        merged.push(arr1.shift(), arr2.shift());
      }
    }
    return [...merged, ...arr1, ...arr2];
  }
}

時間複雜度:

最佳/平均/最差時間複雜度都是：O(nlog n)

不斷分割陣列的部分為 O(log n)，然後兩個陣列比較元素大小並合併為 O(n)，所以時間複雜度為 O(nlog n)

本次程式碼在以下連結:
https://github.com/a90100/javascript-data-structure/blob/master/day20-merge-sort.js

明天將會介紹最後一種排序法，快速排序法!