12、归并排序

[fudx]

    let arr = [1,2,4,3,23,54,12,345,90]

[fudx]

let arr = [1,2,4,3,23,54,12,345,90]
    function mergeSort(arr){
        if(arr.length <= 1) return arr
        const p = arr.length >> 1
        const sortLeft = mergeSort(arr.slice(0,p))
        const sortRight = mergeSort(arr.slice(p))
        return merge(sortLeft,sortRight)
    }
    function merge(left,right) {
        let l1 = 0,l2 = 0,result = []
        while(l1 < left.length && l2 < right.length) {
            if(left[l1] < right[l2]) {
                result.push(left[l1])
                l1++
            }
            else {
                result.push(right[l2])
                l2++
            }
        }
        if(l1 > left.length - 1) {
            result.push(...right.slice(l2))
        } 
        else {
            result.push(...left.slice(l1))
        }
        return result
    }

    console.log(mergeSort(arr)) // 1, 2, 3, 4, 12, 23, 54, 90, 345