day-27 使用js实现归并排序

function mergeSort(arr){
    if (arr.length < 2) return arr;
    let middle = Math.floor(arr.length / 2);
    let left = arr.slice(0, middle);
    let right = arr.slice(middle, arr.length);
    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
    let res = [];
    while (left.length && right.length) {
        if (left[0] <= right[0]) {
            res.push(left.shift())
        } else {
            res.push(right.shift())
        }
    }
    while (left.length) {
        res.push(left.shift());
    }
    while (right.length) {
        res.push(right.shift());
    }
    return res
}

let arr = [8, 4, 5, 3, 2, 9, 4, 16, 6]
console.log('old', arr);
arr = mergeSort(arr);
console.log('new',arr)