编辑代码

let cnt = 0;

/**
 * @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++]);
            cnt += mid - i + 1;
        }
    }
    /* 合并剩下元素 */
    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 = [2, 4, 3, 1, 5, 6];
const left = 0;
const right = arr.length - 1;
mergeSort(arr, left, right);
console.log('逆序对个数: ', cnt);