Sort an array given the number of inversions

Question

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.

Answer 1

What about the following algorithm.

Let's start with $A[0]$ and compare it with the following element. If next element is larger - move forward: compare $A[1]$ and $A[2]$. The part of the array behind us is sorted. If at some step we found $A[m] > A[m+1]$ - remember current position, swap the two elements. The number of inversions decreases by 1. Now we would need to check the previous pair, if it is inverted, swap them, and so on. Each step decreases number of inversions by 1. As soon as the previous pair is not inverted we can return to the remembered position: the part of array up to remembered position is sorted.

So, there are two types of steps: first type moves remembered position forward by one element, second type swaps two elements in the part of array up to the remembered position.

We will have to make exactly $n$ operations of the first type and exactly $k$ operations of the second type (because swap of two adjacent elements decreases the number of inversions exactly by one). So, the complexity of this algorithm is $θ(n + k)$.

I guess this is bubble sort.