Sort array in Θ(n) complexity

Question

Prove that an array A of size n can be sorted in Θ(n) when it has O(n) inversions.

I don't know exactly what this question is asking. My best guess is that we use insertion sort on a presorted input and that way we can achieve Θ(n) complexity by sorting. Is this what the question is asking me?

Answer 1

As a hint - the runtime of insertion sort is Θ(n + I), where n is the number of elements and I is the number of inversions in the array. What happens if you insertion sort the array, given that it only has O(n) inversions? What will the time complexity be?

Hope this helps!