const mergeSort = arr => {
// 采用自上而下的递归方法
const len = arr.length;
// 递归条件
if (len < 2) {
return arr;
}
let middle = Math.floor(len / 2),
left = arr.slice(0, middle),
right = arr.slice(middle); // 拆分为两个子数组
return merge(mergeSort(left), mergeSort(right));
};
// 合并两个已经排好序的数组，无论left或者right里有多少元素
const merge = (left, right) => {
const 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;
};
