分解javascript归并排序

掌握算法，先理解原理

采用分而治之的策略
拆分 --> 取值 --> 合并

把长度为n的输入序列分成两个长度为n/2的子序列；
对这两个子序列分别采用归并排序；
将两个排序好的子序列合并成一个最终的排序序列。

归并排序.jpg

function mergeSort(arr) {  // 采用自上而下的递归方法
    var len = arr.length;
    if (len === 1) {
        return arr;
    }
    var middle = Math.floor(len / 2), //去中间点
        left = arr.slice(0, middle),  // 左数组
        right = arr.slice(middle); // 右数组
    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
    var result = [];

    while (left.length>0 && right.length>0) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }
    /* 当左右数组长度不等.将比较完后剩下的数组项链接起来即可 */
    return result.concat(left).concat(right);

}
var array = [11, 43, 24, 76, 89, 43, 65]

console.log(mergeSort(array))

参考文章：
归并排序