合併排序是一種使用「分治法」概念的排序算法。
給定一個數組，我們首先將其分為兩個數組。
然後我們遞歸執行此操作，直到獲得只有一個元素的數組。
然後，我們從頭開始構建有序數組，通過對獲得的個別元素進行排序。
假設我們的數組是：
[4, 3, 1, 2]
我們首先將數組分成兩個：
[4, 3]
[1, 2]
然後我們遞歸地分割這些數組：
[4]
[3]
和
[1]
[2]
然後，通過首先對這些元素對進行排序，我們開始構建結果：
[3, 4]
[1, 2]
然後我們將這兩個數組合併：
[1, 2, 3, 4]
讓我們再舉一個具有更多項的數組的例子，這次使用字母：
['e', 'g', 'a', 'd', 'f', 'c', 'b']
我們將數組分成兩部分：
['e', 'g', 'a']
['d', 'f', 'c', 'b']
然後我們將第一個數組再分成兩部分：
['e']
['g', 'a']
然後分割第二個結果：
['g']
['a']
我們現在取原始數組的第二部分，再分成兩個：
['d', 'f']
['c', 'b']
我們分割兩個項目：
['d']
['f']
['c']
['b']
現在，我們有一系列只有一個元素的數組：
['e']
['g']
['a']
['d']
['f']
['c']
['b']
現在，我們將它們按成對排序：
['e', 'g']
['a', 'd']
['d', 'f']
['c', 'b']
然後我們對前兩個數組和最後兩個數組進行排序：
['a', 'd', 'e', 'g']
['c', 'b', 'd', 'f']
最後，我們合併獲得的兩個數組：
['a', 'b', 'c', 'd', 'e', 'f', 'g']
我們可以使用兩個函數來實現此算法。第一個叫做 mergeSort，這是我們將要調用的函數，另一個叫做 _mergeArrays，它負責合併數組。我在它的名字前加了 _，表示它不應該直接調用。
以下是實現的代碼：
const _mergeArrays = (a, b) => {
const c = [];
while (a.length && b.length) {
c.push(a[0] > b[0] ? b.shift() : a.shift());
}
// 如果還有值，將其添加到 `c` 的末尾
while (a.length) {
c.push(a.shift());
}
while (b.length) {
c.push(b.shift());
}
return c;
}
const mergeSort = (a) => {
if (a.length < 2) return a;
const middle = Math.floor(a.length / 2);
const a_l = a.slice(0, middle);
const a_r = a.slice(middle, a.length);
const sorted_l = mergeSort(a_l);
const sorted_r = mergeSort(a_r);
return _mergeArrays(sorted_l, sorted_r);
}
請注意，在 _mergeArrays() 函數中，我們初始化一個結果數組 c，並通過將傳遞給函數的 a 和 b 數組的值按值排序來填充它。在數組上調用 shift() 會刪除數組的第一個項目並返回該項目，因此我們將其傳遞給 c.push() 來將其添加到 c 數組中。
該算法的時間複雜度是 O(n log(n))，因此它非常高效。