Question: what is the relationship between the running time of insertion sort and the number of inversions?
Answer: The running time of insertion sort is a constant times the number of inversions. Let I ( i ) I(i) I(i) denote the number of j < i j < i j<i such that A [ j ] > A [ i ] A[j] > A[i] A[j]>A[i]. Then ∑ i = 1 n I ( i ) \sum_{i = 1}^n I(i) ∑i=1nI(i) equals the number of inversions in A.