### Relation between running time of insertion sort and number of inversions in an array mergesort sorting noofinversion insertionsort timecomplexity array    Posted: 7 years ago Updated: 6 years ago Edit answers (1) views (8846)

Suppose you are applying insertion sort on an array. How will you relate its running time with the number of inversions?

 Posted: 7 years ago 0 0 Edit An inversion in an array a[ ] is a pair of entries a[i] and a[j] such that i < j and a[i] > a[j] . The number of inversions w.r.t the current element, a[i] , is $$c_i-1$$, at each iteration, where $$c_i$$ is the number of comparisons. If the total number of inversions ( Counting Inversions problem ) is $$N_i$$, running time of insertion sort is $$O(n+N_i)$$.