What is Inversions?
Inversion are sequence of number $\left ( A\left [ i \right ],A\left [ j \right ] \right ),where A\left [ i \right ]> A\left [ j \right ],where \, i< j$
Maximum number of inversions in an array of size $n=\left ( n-1 \right )+\left ( n-2 \right )\cdots +1=\left ( n^{2}-n \right )/2$
In an Insertion sort,the outer loop runs for n times and inner loop runs to find $A\left [ i \right ]> A\left [ j \right ]\, ,i< j$ and then swaps it which is nothing but Number of inversions.
Taske an example
array in decreasing order,$A=\left \{ 5,4,3,2,1 \right \}$, here each time inner loop will find an inversion as $A\left [ 1 \right ]> A\left [ 2 \right ],1< 2$ and in the worst case(in this case only) it will count number of inversion in $O\left ( n^{2}\right )$
Hence complexity of insertion sort is $\Theta \left ( n+d \right )$ where d= number of inversions
