SOURCE

const array = [2, 5, 3, 2, 6, 10, 7, 5, 8]
unionSort(array)
console.log(array)


function unionSort(arr) {
    let temp = new Array(arr.length).fill(0)
    sort(arr, 0, arr.length - 1, temp)
}

function sort(arr, left, right, temp) {
    if (left < right) {
        let mid = Math.floor(left + (right - left) / 2)
        sort(arr, left, mid, temp)
        sort(arr, mid + 1, right, temp)
        merge(arr, left, mid, right, temp) // 将两个有序子数组合并操作
    }
}
function merge(arr, left, mid, right, temp) {
    let i = left
    let j = mid + 1
    let t = 0
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[t++] = arr[i++]
        } else {
            temp[t++] = arr[j++]
        }
    }
    while (i <= mid) {//将左边剩余元素填充进temp中
        temp[t++] = arr[i++]
    }
    while (j <= right) {//将右序列剩余元素填充进temp中
        temp[t++] = arr[j++]
    }
    t = 0
    //将temp中的元素全部拷贝到原数组中
    while (left <= right) {
        arr[left++] = temp[t++]
    }
}