玖叶教程网

归并排序概念：

归并排序中涉及到一个概念就是分而治之，总序列化成小序列，将小序列排序好，利用排序好的小序列，再归并排序成原来要排序的序列。

所以排序前先要分：

function divide( arr ){
    let len = arr.length;
    if( !len ) return;
    let left = arr.splice(0, Math.floor(len/2) ),
        right = arr;
}

分完之后要合并,我们默认从小到大排序哈，

 function range ( left ,right ){
     let result = [];
     while( left.length && right.length){
         if( left[0] > right[0] ){
             result.push( right.shift() )
         }else{
             result.push( left.shift() )
         }
     }
     while( left.length ){ 
         result.push( left.shift() )
     }
     while( right.length ){
         result.push( right.shift() )
     }
     return result;
 }

然后我们需要将两个方法合并一下，为了保存我们已经排序好的子序列结果，我们在分割方法那儿使用了递归--调用自身和合并方法，最小子序列要为1，所以两个方法最终可以写成：

function rangeSort( arr ){
    if( !arr.length ) return;
    function divide( arr ){
        let len = arr.length;
        if( len < 2 ) return arr;
        let left = arr.splice(0, Math.floor(len/2) ),
            right = arr;
         return range( divide(left),divide(right) )//难点
    }
    function range ( left ,right ){
         let result = [];
         while( left.length && right.length){
             if( left[0] > right[0] ){
                 result.push( right.shift() )
             }else{
                 result.push( left.shift() )
             }
         }
         while( left.length ){ 
             result.push( left.shift() )
         }
         while( right.length ){
             result.push( right.shift() )
         }
         return result;
     }
     return divide( arr );
}

归并排序在要处理的数量级达到某个级别之后（并不是很大），性能摔冒泡排序好几条街，至于为啥快，你可以说成是伟大哲学思想的指导，这样是没错，不过我觉得还是因为计算机结构就是这样吧。

以上内容是看完某个大佬的博文，自己一边理解一边实现的，实话实说，因为已经写得很好了，我就不打算用for再重写了，以免误导到人。