前端排序算法 - 归并排序算法 （1）

1. 先将数组一直进行折半拆分 拆到长度为一的数组 
比如 
[ 5 ] [ 6 ]  [ 3 ] [ 1 ] 
2. 再拆分的个体进行两两合并 用 merge 方法
得到 

[ 5, 6 ] 和 [ 1, 3 ]

再将这两个数组进行合并 得到 

[1, 3 , 5, 6]

这个时候左边合并完成  

进行右边拆分合并


[ 8 ] [ 7 ] 和 [ 2 ] [ 4 ] 

得到 

[2, 4 , 7 , 8 ]

所以我们这个时候得到两个数组 

[1, 3 , 5, 6] 和  [2, 4 , 7 , 8 ]

对这两个数组进行合并 得到最后结果 

1,2,3,4,5,6,7,8

let data = [5, 6, 3, 1, 8, 7, 2, 4]
console.log(mergeSort(data))
function mergeSort (arr) {
    var len = arr.length;
    if(len < 2) {
        return arr;
    }
    let middle = Math.floor(len/2);
    let left = arr.slice(0, middle)
    let right = arr.slice(middle)
    return merge(mergeSort(left), mergeSort(right))
}
function merge(left, right) {
    let result = []
    while (left.length> 0 && right.length> 0) {
        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;
}