---
tags: DSA in JavaScript
---
# Ch.15 Merge Sort
> 開始來到稍微複雜的部份了

第一次看到合併排序時，真的是打破了我對於排序法的想像，沒想到遞迴可以在這裡用的如此出神入化。(我現在還只會費式數列而已😅)。

介紹完各種使用巢狀 for loop 完成的排序法之後，接著就要開始介紹稍微再快一點的排序法了。
Merge Sort (合併排序) 是前幾篇提到的 divide and conquer 解題法的體現之一

- 不斷地將陣列一分為二，直到這些陣列的長度變成 0 或 1。
- 把這些碎片化的陣列倆倆比對，合併成前一種狀態
- 不斷地比對、合併，直到回到最初的長度

而這種不斷分裂與合併的過程都是使用遞迴，因此程式碼雖然有點難理解，但是本體比較簡潔 (不談論 helper function)。

先來搞定合併的部分

function merge (arr1, arr2) {
  let ptr1 = 0
  let ptr2 = 0
  const result = []
  // 對兩個 arr 使用 while loop，直到其中一邊結束遍歷
  while (ptr1 < arr1.length && ptr2 < arr2.length) {
  // 把較小的元素放到 result 裡面，同時讓該陣列的指標往下一格移動
    if (arr1[ptr1] < arr2[ptr2]) {
      result.push(arr1[ptr1++])
    } else {
      result.push(arr2[ptr2++])
    }
  }
  // 如果是 arr1 遍歷完的話，代表 arr2 剩下的部分都比 arr1 大，全部加進 result 裡面
  // 因為兩個陣列都是以「已排序」的前提進入函式內，所以不需擔心其餘部分的排序問題
  const rest = ptr1 < arr1.length ? arr1.slice(ptr1) : arr2.slice(ptr2)

  return result.concat(rest)
}

再來就是重頭戲的部分，長度 1 或 0 的陣列代表已經排序過了所以直接回傳。

function mergeSort (arr) {
  if (arr.length <= 1) return arr
  // 小技巧：使用位元轉換可以達到 Math.floor( number / 2) 的效果
  const mid = arr.length >> 1
  // 剩下的部分就交給遞迴處理了
  const left = mergeSort(arr.slice(0, mid))
  const right = mergeSort(arr.slice(mid))
  return merge(left, right)
}

使用了遞迴的合併排序，時間複雜度為 O (${n} log{_2}{n}$)，n 是因為將元素一個個比對，$log{_2}{n}$ 則是不斷將陣列一分為二的次數。而合併時有用到額外的陣列，因此空間複雜度是 O(n)。