There is given sequence $a_1,...a_n$ such that there are $O(n^{\frac{3}{2}}) $ inversions in this sequence. I am thinking about sorting algorithm for that.  I know lower bound for number of comparisons - it is $O(n)$ - on the contrary, there would be a minimum finding algorithm faster than $O(n)$.  Nevertheless, I don't have idea how sort it in linear time ? What doy you think ?Inversion is a pair $(i, j)$ such that $i < j$ and  $a_i > a_j$
Sorting sequence with $O(n^{\frac{3}{2}})$ inversions
sorting