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$

  • $\begingroup$ What is an inversion? $\endgroup$
    – usul
    Oct 6 '15 at 14:16
  • $\begingroup$ inversion is a pair $(i, j)$ such that $i < j$ and $a_i > a_j$ $\endgroup$
    – user40545
    Oct 6 '15 at 14:17
  • $\begingroup$ 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? $\endgroup$
    – usul
    Oct 6 '15 at 15:38
  • $\begingroup$ Yes, intuiton is that large part is arleady sorted. However I don't know how to use this fact. $\endgroup$
    – 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.

  • $\begingroup$ Thanks for reply. However, I don't understand your algorithm. Tell more please. And what's is lower bound ? $\endgroup$
    – user40545
    Oct 6 '15 at 21:38
  • $\begingroup$ @user40545 : $\:$ He didn't give an algorithm. $\;\;\;\;$ $\endgroup$
    – user6973
    Oct 6 '15 at 22:13
  • $\begingroup$ I am not sure if I understand it correctly. You shown that it impossible to sort faster than $\Omega(n \log n)$. yes ? $\endgroup$
    – user40545
    Oct 7 '15 at 14:05
  • $\begingroup$ 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. $\endgroup$ Oct 7 '15 at 17:10
  • 5
    $\begingroup$ @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. $\endgroup$
    – Clement C.
    Oct 8 '15 at 13:57

This is a topic of "adaptive sorting." As a starter, see the wikipedia page https://en.wikipedia.org/wiki/Adaptive_sort .

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.

  • 1
    $\begingroup$ 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$. $\endgroup$ Oct 8 '15 at 13:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.