let cnt = 0;
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];
}
}
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);