编辑代码

function mergeSort(arr) {
    if (arr.length <= 1) {
        return [arr, 0]; // 返回数组和逆序对的个数
    }

    const middle = arr.length >> 1;

    let left = arr.slice(0, middle);
    let right = arr.slice(middle);

    const [sortedLeft, leftCount] = mergeSort(left);
    const [sortedRight, rightCount] = mergeSort(right);

    const [mergedArr, mergeCount] = merge(sortedLeft, sortedRight);

    return [mergedArr, leftCount + rightCount + mergeCount];
}



function merge(left, right) {
    const mergedArr = [];
    let leftIndex = 0,
        rightIndex = 0;
    let count = 0; // 逆序对的个数

    while (leftIndex < left.length && rightIndex < right.length) {
        if (left[leftIndex] > right[rightIndex]) {
            mergedArr.push(right[rightIndex]);
            rightIndex++;
            count += left.length - leftIndex;
        } else {
            mergedArr.push(left[leftIndex]);
            leftIndex++;
        }
    }

    while (leftIndex < left.length) {
        mergedArr.push(left[leftIndex]);
        leftIndex++;
    }

    while (rightIndex < right.length) {
        mergedArr.push(right[rightIndex]);
        rightIndex++;
    }

    return [mergedArr, count];
}



const [sortedArr, count] = mergeSort([2, 4, 3, 1, 5, 6]);
console.log(count);