特點：
- 時間復(fù)雜度：O(nlog2n)
- 歸并排序是穩(wěn)定的排序算法
原理：（分治法）
- 原理類似于合并兩條有序鏈表
- 分割為多條小的有序隊列捧存，通過兩兩合并最終實現(xiàn)完整序列
代碼實現(xiàn)：（遞歸）
// 采用自上而下的遞歸方法
function mergeSort(arr) {
const len = arr.length;
if (len < 2) return arr;
const middle = Math.floor(len >> 1);
const left = arr.slice(0, middle);
const right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
let result = [];
while (left.length && right.length) {
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;
}
