<p>You can't sort it in linear time.</p>

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

<p>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.  </p>

CC BY-SA 3.0
2015-10-06T21:38:45.527Z
Thanks for reply. However, I don't understand your algorithm. Tell more please. And what's is lower bound ?
user40545
CC BY-SA 3.0
2015-10-07T14:05:27.300Z
I am not sure if I understand it correctly. You shown that it impossible to sort faster than $\Omega(n \log n)$. yes ?
user40545
CC BY-SA 3.0
2015-10-07T17:10:44.060Z
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 
CC BY-SA 3.0
2015-10-07T18:16:39.580Z
Is it ok to say: $O(n\log\sqrt n) = \Theta(n\log n)$ ?
user40545
CC BY-SA 3.0
2015-10-08T13:57:07.333Z
@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.
CC BY-SA 3.0
2015-11-14T18:21:21.153Z
I still don't understand. You said that we need $\sqrt{n}\log(\sqrt{n})$ comparisons. However, it is not truth, given lower bound for sorting problem I need $\Omega(n\log \sqrt{n})$.  So this proof doesn't work
user40545
CC BY-SA 3.0
2015-11-14T18:47:39.280Z
You have $\sqrt{n}$ sorting problems. Each one takes $\sqrt{n} \log \sqrt{n}$ comparisons to solve. **MULTIPLY** $(\sqrt{n})$ by $(\sqrt{n} \log {\sqrt{n}})$, and you get a lower bound of $\frac{1}{2} n \log n$ comparisons.
Peter Shor 
CC BY-SA 3.0
2015-10-06T21:14:50.283Z
2015-10-06T21:14:50.283Z
Peter Shor 
<p>This is a topic of "adaptive sorting." As a starter, see the wikipedia page <a href="https://en.wikipedia.org/wiki/Adaptive_sort" rel="nofollow">https://en.wikipedia.org/wiki/Adaptive_sort</a> .</p>

<p>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.</p>

CC BY-SA 3.0
2015-10-08T13:37:21.177Z
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
CC BY-SA 3.0
2015-10-07T00:57:56.563Z
2015-10-08T13:35:05.780Z
2015-10-08T13:35:05.780Z
Yoshio Okamoto
<p>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.  </p>

<p>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)$.  </p>

<p>Nevertheless, I don't have idea how sort it in linear time ? What doy you think ?</p>

<p>Inversion is a pair $(i, j)$ such that $i &lt; j$ and  $a_i &gt; a_j$</p>

CC BY-SA 3.0
2015-10-06T14:16:25.537Z
What is an inversion?
usul
CC BY-SA 3.0
2015-10-06T14:17:21.787Z
inversion is a pair $(i, j)$ such that $i < j$ and  $a_i > a_j$
user40545
CC BY-SA 3.0
2015-10-06T15:38:37.907Z
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
CC BY-SA 3.0
2015-10-06T16:47:56.863Z
Yes, intuiton is that large part is arleady sorted. However I don't know how to use this fact.
user40545
<sorting>
Sorting sequence with $O(n^{\frac{3}{2}})$ inversions
user40545
# Sorting sequence with $O(n^{\frac{3}{2}})$ inversions

(Asked by: username_0 on 2015-10-06)

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$

**Tags:** sorting

> **Comments:**
> **username_1**: What is an inversion?  
> **username_0**: inversion is a pair $(i, j)$ such that $i < j$ and  $a_i > a_j$  
> **username_1**: 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?  
> **username_0**: Yes, intuiton is that large part is arleady sorted. However I don't know how to use this fact.  

---

## 2 answers

### Answer by username_2 on 2015-10-06. Score: 13

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.

> **Comments:**
> **username_0**: Thanks for reply. However, I don't understand your algorithm. Tell more please. And what's is lower bound ?  
> **username_0**: I am not sure if I understand it correctly. You shown that it impossible to sort faster than $\Omega(n \log n)$. yes ?  
> **username_2**: 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.  
> **username_0**: Is it ok to say: $O(n\log\sqrt n) = \Theta(n\log n)$ ?  
> **username_3**: @username_0 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.  
> **username_0**: I still don't understand. You said that we need $\sqrt{n}\log(\sqrt{n})$ comparisons. However, it is not truth, given lower bound for sorting problem I need $\Omega(n\log \sqrt{n})$.  So this proof doesn't work  
> **username_2**: You have $\sqrt{n}$ sorting problems. Each one takes $\sqrt{n} \log \sqrt{n}$ comparisons to solve. **MULTIPLY** $(\sqrt{n})$ by $(\sqrt{n} \log {\sqrt{n}})$, and you get a lower bound of $\frac{1}{2} n \log n$ comparisons.  

---

### Answer by username_4 on 2015-10-07. Score: 8

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.

> **Comments:**
> **username_5**: 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$.  

---

