歸并也使用了分治的思想，并且可以使用 `遞歸` 實現。
圖示：
~~~
// 拆分原數組，一半一半的拆分成左右兩個數組
function mergeSort(arr) {
// 當分的只剩一個時直接返回
if(arr.length<2) {
return arr
}
// 取中間位置
let midPos = parseInt(arr.length/2)
// 拆分成兩個子數組
let left = arr.slice(0, midPos)
let right = arr.slice(midPos)
// 合并兩個分支
return merge(mergeSort(left), mergeSort(right))
}
// 合并兩個數組（按升序合并）
function merge(left, right) {
// 定義一個額外的數組，用來實現合并,這個數組的長度就是原數組的長度 n,所有空間復雜度是 O(n)
let result = []
while(left.length && right.length) {
// 如果左邊小就彈出左邊的第1個元素放到 result 中，否則彈出右邊的第1個元素放到 result 中
if(left[0]<right[0]) {
result.push(left.shift())
} else {
result.push(right.shift())
}
}
// 如果左邊還剩有元素
while(left.length) {
result.push(left.shift())
}
while(right.length) {
result.push(right.shift())
}
return result
}
~~~
