SOURCE

// 归并排序

function mergeSort(arr) {
    var len = arr.length;
    // 递归的终止条件
    if (len < 2) {
        return arr;
    }
    var mid = Math.floor(len/2);
    var left = arr.slice(0,mid);
    var right = arr.slice(mid);
    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
    var result = [];
    while (left.length && right.length) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }
    // 子序列长度为奇数的情况，此时做比较后会有多出来的一个值无法进行上述的判断
    while (left.length) {
        result.push(left.shift());
    }
    while (right.length) {
        result.push(right.shift());
    }
    return result;
}

var arr = [20,0,39,66,40,78,46,36,60,100];
newArr = mergeSort(arr);
console.log(newArr);

//  快速排序

function quickSort(arr) {
    var length = arr.length;
    if (length <= 1) {
        return arr;
    }
    var base_num = arr[0];
    var left = [];
    var right = [];
    for (var i=1; i<length; i++) {
        if (arr[i] < base_num) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }
    left = quickSort(left);
    right = quickSort(right);
    return left.concat([base_num], right);
}

newArr2 = quickSort(arr);
console.log(newArr2);