How can I quantify the number of swaps required for insertion sort?
It is a classic exercise to relate the running time of insertion sort to the number of inversions in the input. An inversion is a pair of indices $i &lt; j$ such that $A[i] &gt; A[j]$. The number of comparisons made by insertion sort when there are $I$ inversions is always between $I$ and $I+n-1$.