Counting inversions in an array of 1 to N Is there a straightforward way to characterise the number of inversions in an array of length N having distinct elements, each element an integer from 1 to N?

It's for a constraint optimization problem, where the number of inversions needs to be minimized.
You can count inversions efficiently by adapting mergesort, but the most intuitive way is to just count all pairs:

$$\text{inv}(A) = \sum_{i=1}^{|A|}\sum_{j=i+1}^{|A|}[A_j&lt;A_i]$$

Where $[A_j &lt; A_i] = 1$ when $A_j &lt; A_i$ and $0$ otherwise.