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

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