JavaScript 归并排序

Question

归并排序（Merge Sort）是一种基于分治思想的排序算法，其基本思路是将一个大问题分解成若干个小问题，然后逐一解决这些小问题，最后将它们合并起来，得到最终的解。具体实现过程如下：

• 将待排序数组不断二分，直到每个子数组只剩一个元素。
• 将相邻的两个子数组合并成一个有序的子数组，直到所有子数组都被合并成一个有序数组。

时间复杂度 nlog(n)

function mergeSort(arr) {
    if (arr.length <= 1) {
        return arr
    }

    const mid = Math.floor(arr.length / 2)
    const left = arr.slice(0, mid)
    const right = arr.slice(mid)

    const sortLeftArr = mergeSort(left)
    const sortRightArr = mergeSort(right)

    return merge(sortLeftArr, sortRightArr)
}

function merge(leftArr, rightArr) {
    const res = []
    let leftIdx = 0
    let rightIdx = 0
    // 当一个数组遍历完成 另一个数组的值 都大于 res中的值
    while (leftIdx < leftArr.length && rightIdx < rightArr.length) {
        if (leftArr[leftIdx] < rightArr[rightIdx]) {
            res.push(leftArr[leftIdx])
            leftIdx++
        } else {
            res.push(rightArr[rightIdx])
            rightIdx++
        }

    }
    // 合并 res 和剩余的数组的值
    return res.concat(leftArr.slice(leftIdx)).concat(rightArr.slice(rightIdx))

}

console.log(mergeSort([1, 2, 5, 3, 2, 1, 10, 20, 1]))