# Sorting sequence with $O(n^{\frac{3}{2}})$ inversions

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$

• What is an inversion? – usul Oct 6 '15 at 14:16
• inversion is a pair $(i, j)$ such that $i < j$ and $a_i > a_j$ – user40545 Oct 6 '15 at 14:17
• Hmm, can you expand on the consequences of this $n^{\frac{3}{2}}$ upper bound? It seems like a large part of the sequence must already be sorted? – usul Oct 6 '15 at 15:38
• Yes, intuiton is that large part is arleady sorted. However I don't know how to use this fact. – user40545 Oct 6 '15 at 16:47

You can't sort it in linear time.

Suppose you have $n$ items, and you divide them into $\sqrt{n}$ consecutive blocks of $\sqrt{n}$ items each.

You need to take $\sqrt{n} \log \sqrt{n}$ comparisons to sort each one. And there are $\sqrt{n}$ of them, giving $\theta(n \log n)$ time total. And it's easy to see that there can't be more than $n^{3/2}$ inversions in the sequence, since there can't be more than $n$ inversions in each subsequence.

• Thanks for reply. However, I don't understand your algorithm. Tell more please. And what's is lower bound ? – user40545 Oct 6 '15 at 21:38
• @user40545 : $\:$ He didn't give an algorithm. $\;\;\;\;$ – user6973 Oct 6 '15 at 22:13
• I am not sure if I understand it correctly. You shown that it impossible to sort faster than $\Omega(n \log n)$. yes ? – user40545 Oct 7 '15 at 14:05
• That's right. Even if there are only $n^{3/2}$ inversions, you can't sort using fewer than $\frac{1}{2} n \log n$ comparisons. – Peter Shor Oct 7 '15 at 17:10
• @user40545 No, it's not. If you had $\Theta$ on both side, or $O$ on both sides, yes -- but what you wrote, with the $O(\cdot)$ and one side and the $\Theta(\cdot)$ on the other is wrong. – Clement C. Oct 8 '15 at 13:57

It is known that we can sort a sequence of length $n$ with $k$ inversions with $O(n \log (2+k/n))$ comparisons. When $k=O(n^{3/2})$, this translates to $O(n \log n)$. We also have a lower bound of $\Omega(n \log (2+k/n))$. Thus, we know a linear bound is impossible.
• I took the liberty to fix the bound. The original implied that sorting can be done with $O(k)$ comparisons, which is easily seen to be impossible for $1\le k\ll n$. – Emil Jeřábek Oct 8 '15 at 13:37