概念
归并排序(merge sort) 是建立在归并操作上的一种有效的排序算法。
该方法是采用分治法的一种非常典型的应用，将已经有序的序列合并，得到完整的有序的序列。
归并排序.png
步骤：
百科例子 设有数列{6，202，100，301，38，8，1}
将数列分解成单个：6,202,100,301,38,8,1
第一次归并后：{6,202},{100,301},{8,38},{1}，比较次数：3；
第二次归并后：{6,100,202,301}，{1,8,38}，比较次数：4；
第三次归并后：{1,6,8,38,100,202,301},比较次数：4；
总的比较次数为：3+4+4=11；
时间复杂度： 平均时间复杂度为O(n log n) 。
算法稳定性：是一个稳定的排序算法。
算法实现
function mergeSort(arr) {
// 判断是否是数组，不是则抛出错误
if(!Array.isArray(arr)) throw new Error('传入的不是数组')
const len = arr.length;
// 判断长度是否小于等于1，是则直接返回
if(len <= 1) return arr;
//将数据分成左右组，对左右两组接着分组，直到数据长度为1，再进行合并
const middle = Math.floor(len / 2),
left = arr.slice(0,middle),
right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right))
}
function merge(left, right) {
let result = [];
while(left.length > 0 && right.length > 0) {
// 左边的第一个元素和右边的第一个元素比较，大于的添加进入
// 小于等于的话将left的第一个之加入
if(left[0] > right[0]) {
result.push(right.shift());
} else {
result.push(left.shift());
}
}
return result.concat(left).concat(right)
}
