javascript归并排序

基本思想：先进行划分，然后再进行合并。

例如：要对数组进行归并排序步骤

1. 先将C划分为两个数组A和B（即把数组C从中间分开）
2. 再分别对数组A、B重复步骤1的操作，逐步划分，直到不能再划分为止(每个子数组只剩下一个元素)，这样，划分的过程就结束了。
如：              [12 20 30 21 15 33 26 19 40 25]
划分为:  [12 20 30 21 15]                [33 26 19 40 25]
           [12 20]      [30 21 15]       [33 26]       [19 40 25]
         [12]  [20]   [30]  [21 15]     [33]  [26]    [19]    [40 25]
         [12]  [20]   [30] [21] [15]    [33]  [26]    [19]   [40] [25]
3. 然后从下层往上层不断合并数组，每一层合并相邻的两个子数组，合并的过程是每次从待合并的两个子数组中选取一个最小的元素，然后把这个元素放到合并后的数组中，不断重复直到把两个子数组的元素都放到合并后的数组为止。

4. 依次类推，直到合并到最上层结束，这时数据的排序已经完成了。

function merge(left,right){
    var tmp=[];
    while(left.length && right.length){
        if(left[0]<right[0]){
            tmp.push(left.shift());
        }
        else{
            tmp.push(right.shift());
        }
    }
    return tmp.concat(left,right);
}
function mergeSort(arr){
    if(arr.length==1){
        return arr;
    }
    var mid=Math.floor(arr.length/2);
    var left=arr.slice(0,mid);
    var right=arr.slice(mid);
    return merge(mergeSort(left),mergeSort(right));
}
console.log(mergeSort([2,3,1,0,9]));