SOURCE

function mergeSort(arr) {

    // 小于等于1的数组直接返回
    if (arr.length <= 1) {
        return arr
    }

    // 1. 获取中间值,并分割数组
    const middleIndex = Math.floor(arr.length / 2)
    const leftArray = arr.slice(0, middleIndex)
    const rightArray = arr.slice(middleIndex)

    // 2. 递归分割左右数组,最后合并(合并在分割之后)
    return merge(mergeSort(leftArray), mergeSort(rightArray))
}

function merge(leftArray, rightArray) {
    // 排序好的数组
    let sortedArray = []

    // 3. 左右都还有元素时,把小的push进去
    while (leftArray.length && rightArray.length) {
        if (leftArray[0] < rightArray[0]) {
            sortedArray.push(leftArray.shift())
        } else {
            sortedArray.push(rightArray.shift())
        }
    }

    // 4. 如果左边或右边还有元素,就放到已排序的数组之后(注意重新赋值,concat不改变原数组)
    if (leftArray.length) {
        sortedArray = sortedArray.concat(leftArray)
    }

    if (rightArray.length) {
        sortedArray = sortedArray.concat(rightArray)
    }

    // 5. 一定记得返回排序好的数组!!!
    return sortedArray

}

const arr = [2, 3, 41, 1, 6, 53, 4, 6, 87, 4]
const res = mergeSort(arr)

console.log(res)