[排序演算法]Merge sort — 合併排序法

發表於 2021-11-26 更新於 2023-12-01 分類於演算法

Merge Sort採用分治法(Divide and Conquer)的方式來處理排序的問題，簡單介紹一下分治法執行的步驟如下:

Merge Sort 採用分治法(Divide and Conquer)的方式來處理排序的問題，簡單介紹一下分治法執行的步驟如下:

Divide:先將大問題不斷切割成小問題
Conquer:用遞迴的方式處理所有的子問題
Combine:將所有的結果合併起來就是最終解答

實作步驟:

將陣列不斷分割，分割到只有一個元素為止，再依照大小依序組合起來，流程可參考下圖

用 js 實作 merge sort

const merge = (arr1, arr2) => {
  const result = [];
  //用雙指針來紀錄比較位置
  let i = 0;
  let j = 0;

  //兩個陣列裡的元素逐一比較大小
  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] > arr2[j]) {
      result.push(arr2[j]);
      j++;
    } else {
      result.push(arr1[i]);
      i++;
    }
  }

  //將剩餘的元素放入result
  while (i < arr1.length) {
    result.push(arr1[i]);
    i++;
  }
  while (j < arr2.length) {
    result.push(arr2[j]);
    j++;
  }
  return result;
};

const mergeSort = (arr) => {
  if (arr.length === 1) return arr;
  //找中間點
  let middle = Math.floor(arr.length / 2);
  //將陣列切為左半邊和右半邊
  let left = arr.slice(0, middle);
  let right = arr.slice(middle, arr.length);
  return merge(mergeSort(right), mergeSort(left));
};

mergeSort([8, 3, 6, 7, 2]);