归并排序
概念：归并排序是一种分治算法。其思想是将原始数组切分成较小的数组，直到每个小数组只有一个位置，接着将小数组归并成较大的数组，直到最后只有一个排序完毕的大数组。
时间复杂度： O(nlogn)
代码实现
var mergeSortRec = function (array) {
var length = array.length;// {1}
if (length === 1) {// {2}
return array;
}
var mid = Math.floor(length / 2), //{3}首先得找到数组的中间位
left = array.slice(0, mid),//{4}左边小数组
right = array.slice(mid, length);//{5}右边小数组
return merge(mergeSortRec(left), mergeSortRec(right));// {6}调用merge函数，它负责合并和排序小数组来产生大数组，直到回到原始数组并已排序完成
}
var merge = function(left, right) {
var result = [], //需要声明归并过程要创建的新数组以及用来迭代两个数组（left和right数组）所需的两个变量
il = 0,
ir = 0;
while (il < left.length && ir < right.length) {//迭代两个数组的过程中
if (left[il] < right[ir]) {// 我们比较来自left数组的项是否比来自right数组的项小。
result.push(left[il++]);// 将该项从left数组添加至归并结果数组，并递增迭代数组的控制变量
} else {
result.push(right[ir++]);// 从right数组添加项并递增相应的迭代数组的控制变量
}
}
while (il < left.length) { // 将left数组所有剩余的项添加到归并数组中
result.push(left[il++]);
}
while (ir < right.length) { // 将right数组所有剩余的项添加到归并数组中
result.push(right[ir++])
}
return result;
}
console.log(mergeSortRec([89,78,9,6765,80,3,6]))
举例：[8,7,6,5,4,3,2,1]
mergeSortRec([8,7,6,5,4,3,2,1])
过程如下图，把大数组递归地分成小数组，再通过小数组排好序合并成大数组。