编辑代码

/**
 * @brief 合并两个有序数组
 * @param arr 
 * @param left 
 * @param mid 
 * @param right 
 */
function merge(arr: number[], left: number, mid: number, right: number): void {
    let i: number = left,
        j: number = mid + 1,
        tmpArr: number[] = [];

    /* 合并两个有序数组 */
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            tmpArr.push(arr[i++]);
        } else {
            tmpArr.push(arr[j++]);
        }
    }
    /* 合并剩下元素 */
    while (i <= mid) tmpArr.push(arr[i++]);
    while (j <= right) tmpArr.push(arr[j++]);

    /* 赋值回原数组 */
    for (let k = 0; k < tmpArr.length; ++k) {
        arr[k + left] = tmpArr[k];
    }
}

/**
 * @brief 归并排序
 * @param arr 
 * @param left 
 * @param right 
 * @returns 
 */
function mergeSort(arr: number[], left: number, right: number): void {
    if (left >= right) return;
    let mid = Math.trunc(left + ((right - left) >> 1));
    /* 分割元素 */
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    /* 归并元素 */
    merge(arr, left, mid, right);
}

const arr = [6, 1, 5, 3, 2, 8, 4, 7, 9]
const left = 0;
const right = arr.length - 1;
console.log('排序前:')
console.log(arr);
mergeSort(arr, left, right);
console.log('排序后:');
console.log(arr);