# algorithms – Inversions of Insertion Sort and Bubble Sort

Let’s consider the swaps performed by insertion sort.
In the $$i$$-th iteration, insertion sort repeatedly swaps the element $$x$$ originally in $$A(i)$$ with some element $$y$$ originally in $$A(1:i-1)$$ until the subarray $$A(1:i)$$ is sorted. Then, since we must have $$x for the swap to occur, we have that each swap induces an inversion in the original array. Notice that the $$i$$-th iteration takes time proportional to $$1+s_i$$ where $$s_i$$ is the number of swaps in the iteration.

If follows that insertion sort takes time $$O(n+sum_{i=1}^n s_i) = O(n + s)$$, where $$s$$ is the number of inversions of $$A$$.
Thus, when insertion sort takes time $$Omega(n^2)$$ we must have $$s=Omega(n^2)$$.

Finally, notice that at most one inversion can be removed by each swap performed by bubble sort, implying that bubble sort takes time $$Omega(s)=Omega(n^2)$$.