# sorting – Sort an array given the number of inversions

Given an array $$A$$ with $$n$$ integers in it, one way of measuring the distance of the array from a sorted array is by counting inversions. A pair of indices $$i,j ∈ {0,…,n−1}$$ is called an inversion if $$i < j$$ and $$A[i] > A[j]$$. If the number of inversions is $$k$$ is it possible to sort the array in $$θ(n + k)$$ steps?

I tried going with the approach of bubble sort, but I couldn’t go ahead with it. Also, if I figure out which sorting technique to use, it would definitely help me out, I guess. Any help is appreciated, thanks.