『算法-ACM 竞赛』归并排序求逆序对

// 归并排序求逆序对
void merge(int l, int mid, int r) {
// 合并 a[l~mid]与 a[mid+1~r]
// a 是待排序数组, b 是临时数组, cnt 是逆序对个数
int i = l, j = mid + 1;
for (int k = l; k <= r; k++)
if (j > r || i <= mid && a[i] < a[j]) b[k] = a[i++];
else b[k] = a[j++], cnt += mid - i + 1;
for (int k = l; k <= r; k++) a[k] = b[k];
}