设A[1..n]是一个包含n个不同数的数组。如果在i<j的情况下，有A[i]>A[j]，则（i,j）就称为A中的一个逆序对。
请给出一个算法，能在O(nlgn)的最坏情况运行时间，确定n个元素的任何排列中逆序对的数目。

我能给出一个O(n2)的算法（naive），但实在想不出O(nlgn)的算法。

int c[LEN],d[LEN],summ=0;
void MergeSort(int p, int r)
{
if (p >= r) return ;
int i, j, v, mid = (p + r) >> 1;
MergeSort(p, mid);
MergeSort(mid + 1, r);
i = p; j = mid + 1; v = 0;
while (i <= mid && j <= r) {
if (c[i] > c[j]) {
d[v++] = c[j++];
summ += mid - i + 1; //inversion
}
else d[v++] = c[i++];
}
while (i <= mid) d[v++] = c[i++];
memcpy(c + p, d, v * sizeof(int));
}
借助归并排序可以求你序

这里(p + r) &gt;&gt; 1，即是(p+r)/2,感得楼上函数有点奇，如果可以麻烦说说它理由。