An inversion in an array A$[1..$ n$]$ is a pair of indices $($i$,$ j$)$ such that i $<$ j and

A$[$i$]>$ A$[$ j$].$ The number of inversions in an n$-$element array is between $0$

$($if the array is sorted$)$ and