排序演算法筆記 4 – Merge Sort (合併排序法)

Merge Sort (合併排序法) 是第一個要介紹的 efficient sort，和前面幾個排序演算法相比雖然會複雜一些，但時間複雜度相較之下也會比較好。

1. Merge Sort 方法一

1.1 JavaScript 實作

function mergeSort1(arr) {
  if (arr.length < 2) {
    return arr;
  } else {
    // 將陣列切半
    const middle = Math.floor(arr.length / 2);
    const leftArr = arr.slice(0, middle);
    const rightArr = arr.slice(middle, arr.length);
    // 合併排序好的兩半陣列
    return merge1(mergeSort1(leftArr), mergeSort1(rightArr));
  }
}

function merge1(leftArr, rightArr) {
  const result = [];
  let leftIndex = 0;
  let rightIndex = 0;

  while (leftIndex < leftArr.length && rightIndex < rightArr.length) {
    if (leftArr[leftIndex] > rightArr[rightIndex]) {
      result.push(rightArr[rightIndex]);
      rightIndex++;
    } else {
      result.push(leftArr[leftIndex]);
      leftIndex++;
    }
  }

  while (leftIndex < leftArr.length) {
    result.push(leftArr[leftIndex]);
    leftIndex++;
  }

  while (rightIndex < rightArr.length) {
    result.push(rightArr[rightIndex]);
    rightIndex++;
  }

  return result;
}

2. Merge Sort 方法二

2.1 JavaScript 實作

function mergeSort2(arr, start = 0, end = arr.length - 1) {
  if (start === end) {
    return arr;
  } else {
    const middle = Math.floor((start + end) / 2);
    // 排序左半部
    mergeSort2(arr, start, middle);
    // 排序右半部
    mergeSort2(arr, middle + 1, end);
    // 將兩半部排序完的陣列合併
    merge2(arr, start, middle, end);
    return arr;
  }
}

function merge2(arr, start, middle, end) {
  const result = [];
  let leftIndex = start;
  let rightIndex = middle + 1;

  while (leftIndex <= middle && rightIndex <= end) {
    if (arr[leftIndex] < arr[rightIndex]) {
      result.push(arr[leftIndex]);
      leftIndex++;
    } else {
      result.push(arr[rightIndex]);
      rightIndex++;
    }
  }

  while (leftIndex <= middle) {
    result.push(arr[leftIndex]);
    leftIndex++;
  }

  while (rightIndex <= end) {
    result.push(arr[rightIndex]);
    rightIndex++;
  }

  for (let i = start; i <= end; i++) {
    arr[i] = result[i - start];
  }
}

3. Merge Sort 方法三

3.1 JavaScript 實作

function mergeSort3(arr) {
  const n = arr.length;
  for (let i = 1; i <= n; i *= 2) {
    for (let j = 0; j + i < n; j += 2 * i) {
      const start = j;
      const end = Math.min(j + i * 2 - 1, n - 1);
      const mid = j + i - 1;
      merge3(arr, start, mid, end);
    }
  }
  return arr;
}

function merge3(arr, start, middle, end) {
  const result = [];
  let leftIndex = start;
  let rightIndex = middle + 1;

  while (leftIndex <= middle && rightIndex <= end) {
    if (arr[leftIndex] < arr[rightIndex]) {
      result.push(arr[leftIndex]);
      leftIndex++;
    } else {
      result.push(arr[rightIndex]);
      rightIndex++;
    }
  }

  while (leftIndex <= middle) {
    result.push(arr[leftIndex]);
    leftIndex++;
  }

  while (rightIndex <= end) {
    result.push(arr[rightIndex]);
    rightIndex++;
  }

  for (let i = start; i <= end; i++) {
    arr[i] = result[i - start];
  }
}

4. Time Complexity

最佳：O(n log n)
最差：O(n log n)
平均：O(n log n)

4. 參考資料

大話資料結構(全新彩色版)
資料結構與演算法 (JavaScript)
JavaScript 學演算法（九）- 合併排序
一起用 JavaScript 來複習經典排序法吧！