JavaScript归并排序

 思路

以升序排序为例：

1. 归

   把数组分成两半，再递归地对子数组进行“分”操作，直到分成一个个单独的数

2. 并

   把两个数合并为有序数组，再对有序数组进行合并，直到全部子数组合并为一个完整数组

「时间复杂度: O(nlog(n))」

手写实现：

let mergerSort=(array)=>{//功能：将数组分为两半
    if(array.length<=1){//递归出口，数组个数为1
        return array;
    }
    let mid=Math.floor(array.length/2);//取中间值
    let left=array.slice(0,mid);//将数组分为两部分
    let right=array.slice(mid);
    //return mergerSort(left),mergerSort(right)//递归将数组成长度为1的有序子文件(数组内部是有序的)
    return merge(mergerSort(left),mergerSort(right));//递归将有序数组合并
}

let merge=(left,right)=>{//功能：对两个有序数组的并
    let temp=[];
    while(left.length && right.length)
    {
        if(left[0]<right[0])
        temp.push(left.shift());
        else temp.push(right.shift());
    }
    while(left.length){
        temp.push(left.shift());
    }
    while(right.length){
        temp.push(right.shift());
    }
    return temp;
}
let a=[1,5,4,2,6,7];
console.log(mergerSort(a));
[ 1, 2, 4, 5, 6, 7 ]