var mergeSort = function(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));

}
var merge = function(left,right){

var re = [];
while(left.length > 0 && right.length > 0){
    if(left[0] < right[0]){
        re.push(left.shift());
    }else{
        re.push(right.shift());
    }
}
return re.concat(left).concat(right);

}

Firefox 和 Safari 用归并排序实现的 Array.prototype.sort().
所以

    console.log(new Array(1,3,6,4,7,2,9).sort())

将会输出:

Array [ 1, 2, 3, 4, 6, 7, 9 ]

或者抄一个别人的实现

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

    while (il < left.length && ir < right.length){
        if (left[il] < right[ir]){
            result.push(left[il++]);
        } else {
            result.push(right[ir++]);
        }
    }

    return result.concat(left.slice(il)).concat(right.slice(ir));
}

function mergeSort(items){

    // Terminal case: 0 or 1 item arrays don't need sorting
    if (items.length < 2) {
        return items;
    }

    var middle = Math.floor(items.length / 2),
        left    = items.slice(0, middle),
        right   = items.slice(middle);

    return merge(mergeSort(left), mergeSort(right));
}

参考:
https://github.com/nzakas/com...