// 归并排序 // 思路： // 复杂度：时间 O(nlgn) | 空间 O(n)

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

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

// let arr = [1,34,5,56,6,78,0,3]
let arr = [3,1,2,4]
console.log(sortMerge(arr));