Based on the Wikipedia implementation of insertion sort:Given an input array $A$:for i  1 to length(A)    j  i    while j > 0 and A[j-1] > A[j]        swap A[j] and A[j-1]        j  j - 1is there a way to quantify how many swaps are needed to sort the input list? It's $O(n^2)$, but I want a more precise bound. A perfectly sorted array clearly needs no swaps (so insertion sort is $\Omega(n)$), while a completely reversed array requires something on the order of $n^2$ swaps, but how do we quantify the number of swaps?
How can I quantify the number of swaps required for insertion sort?
algorithms;sorting
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 < j$ such that $A[i] > A[j]$. The number of comparisons made by insertion sort when there are $I$ inversions is always between $I$ and $I+n-1$.