08.md

Merge Sort

Definition

核心概念為 "Divide and Conquer"。將 array 對半切分直到長度為 1，之後再倆倆比較，使用 pointer 的概念形成一個已排序array，直到所有元素被排序完畢。必須注意，因為在 merge 過程中會持續產生新的 array，故空間複雜度會比其他排序法更高

Performance

• Worst Case: O(nlogn)
• Best Case: O(nlogn)
• Average Case: O(nlogn)

Code:

function merge(arr1, arr2) {
  const result = [];
  let i = 0;
  let j = 0;
  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] > arr2[j]) { // 若 arr1[i] > arr2[j]
      result.push(arr2[j]); // 把小的值 arr2[j] 放入新的 arrary
      j++;
    } else {
      result.push(arr1[i]);
      i++;
    }
  }
  // 若 i or j 其中一個已經超過 arr.length，表示另外一個 index 剩下來的數值一定是最大，則直接塞到 result 裡
  while (i < arr1.length) {
    result.push(arr1[i]);
    i++;
  }
  while (j < arr2.length) {
    result.push(arr2[j]);
    j++;
  }
  return result;
}

function mergeSort(arr) {
  if (arr.length === 1) {
    return arr;
  }

  const middle = Math.floor(arr.length / 2);
  const left = arr.slice(0, middle);
  const right = arr.slice(middle, arr.length);
  // 使用遞迴法持續切分 array，直到長度為 1，再進行 merge
  return merge(mergeSort(left), mergeSort(right));
}