Can we count the number of inversions in time $\mathcal{O}(n)$?
There are $o(n\log n)$ algorithms in the RAM model. Dietz gave an $O(n\log n/\log\log n)$ algorithm in his 1989 paper Optimal algorithms for list indexing and subset rank, and Chan and Pătraşcu gave an $O(n\sqrt{\log n})$ algorithm in their 2010 paper Counting inversions, offline orthogonal range counting, and related problems. Chan and Pătraşcu also gave an $O(n)$ algorithm for finding a $1+\epsilon$ approximation, for any $\epsilon&gt;0$.

If you only allow comparisons, then there is an $\Omega(n\log n)$ lower bound, see this question on cstheory.