归并也使用了分治的思想，并且可以使用 `递归` 实现。
图示：
~~~
// 拆分原数组，一半一半的拆分成左右两个数组
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
}
~~~
