归并排序

原作者：正月点灯笼

1.基本原理：如何将这两个数组排序并合并到下面数组中

1.合并

arr数组如何排序， 左右分成两个数组
1.首先将整个数组拆成两个数组，i, j分别指向各自头部
k指向arr头部


选择i,j较小的那一个填进arr中，直到有一方数组越界

const merge = (arr, l, r, m) => {
    // 1.split into left and right array
    const left = arr.slice(l, m +1),
        right = arr.slice(m + 1, r + 1)
    //2. merge into the original array i，j, k
    let i = 0, j = 0, k = l
    while (i < left.length && j < right.length) {
        if (left[i] < right[j]) {
            arr[k++] = left[i++]
        } else {
            arr[k++] = right[j++]
        }
    }
    while (i < left.length) {
        arr[k++] = left[i++]
    }
    while (j < right.left) {
        arr[k++] = right[j++]
    }
}

2.分治

如果数组左右都是乱序
左右分别排序然后合并
分治法思想，不断细分直到长度为1说明必是有序的。然后合并

const mergeSort = (arr, l, r) => {
    if (l === r){
        return 
    }
    const m = l + Math.floor((r - l)/2) 
    // log(m)
    mergeSort(arr, l, m)
    mergeSort(arr, m+1, r)
    //保证两个函数用的m是一致的（mergeSort和merge）
    merge(arr, l, r, m)
}

总结
1.拆分
2.合并（归并）
拆成全为1的，合并，再

const merge = (arr, l, r, m) => {
    // 1.split into left and right array
    const left = arr.slice(l, m +1),
        right = arr.slice(m + 1, r + 1)
    //2. merge into the original array i，j, k
    let i = 0, j = 0, k = l
    while (i < left.length && j < right.length) {
        if (left[i] < right[j]) {
            arr[k++] = left[i++]
        } else {
            arr[k++] = right[j++]
        }
    }
    while (i < left.length) {
        arr[k++] = left[i++]
    }
    while (j < right.left) {
        arr[k++] = right[j++]
    }
}
const mergeSort = (arr, l, r) => {
    if (l === r){
        return 
    }
    const m = l + Math.floor((r - l)/2) 
    // log(m)
    mergeSort(arr, l, m)
    mergeSort(arr, m+1, r)
    //保证两个函数用的m是一致的（mergeSort和merge）
    merge(arr, l, r, m)
}
// 测试
const main = () => {
    const arr = [2, 3, 9, 7, 4, 5, 101, 11, 12]
    const l = 0, r = arr.length -1
    // merge(arr, l, r, m)
    mergeSort(arr, l, r)
    log(arr, m)
}
main()

回传值版

const mergeSort = (arr, l, r) => {
    if (l === r) return [arr[l]]
    const m = l + ((r - l) >> 1)
    const left = mergeSort(arr, l, m)
    const right = mergeSort(arr, m + 1, r)
    return merge(left, right)
}

const merge = (left, right) => {
    const res = []
    let p1 = p2 = 0
    let n1 = left.length, n2 = right.length
    while (p1 < n1 && p2 < n2) {
        if (left[p1] >= right[p2]) {
            res.push(left[p1++])
        } else {
            res.push(right[p2++])
        }
    }
    while (p1 < n1) {
        res.push(left[p1++])
    }
    while (p2 < n2) {
        res.push(right[p2++])
    }
    return res
}