<p>Input is a list of <span class="math-container">$n$</span> integers in an array A. Desired output is stored in Array B, such that <span class="math-container">$|rank(B[i])- i | \leq \sqrt{n}$</span>.
Can this be done using <span class="math-container">$O(\log n)$</span> comparisons per element?
Just looking for some unusual tricks, other than finding the <span class="math-container">$\{\sqrt{n}, 2\sqrt{n}\ldots n-\sqrt{n}\}$</span> ranked integers and then partitioning the rest of the elements in these sets.</p>

<p>In simple terms, the desired output is such that every element in the output, should be at most <span class="math-container">$\sqrt{n}$</span> distance away from its sorted location.</p>

CC BY-SA 4.0
2019-09-22T07:12:40.583Z
Using the Ajtai–Komlós–Szemerédi sorting network, you can *completely* sort the array using $O(\log n)$ comparisons per element.
Emil Jeřábek
CC BY-SA 4.0
2019-09-23T07:56:14.200Z
There is also a question for [sorting without an AKS network](https://cstheory.stackexchange.com/q/7131)
japh
CC BY-SA 4.0
2019-10-05T05:41:44.233Z
@japh Thanks, thats exactly what I was looking for. Something which doesnt use networks.
Vk1
<ds.algorithms><sorting>
Can you partially sort using $O(\log n)$ comparisons per element?
Vk1
# Can you partially sort using $O(\log n)$ comparisons per element?

(Asked by: username_0 on 2019-09-22)

Input is a list of $n$ integers in an array A. Desired output is stored in Array B, such that $|rank(B[i])- i | \leq \sqrt{n}$.
Can this be done using $O(\log n)$ comparisons per element?
Just looking for some unusual tricks, other than finding the $\{\sqrt{n}, 2\sqrt{n}\ldots n-\sqrt{n}\}$ ranked integers and then partitioning the rest of the elements in these sets.

In simple terms, the desired output is such that every element in the output, should be at most $\sqrt{n}$ distance away from its sorted location.

**Tags:** ds.algorithms, sorting
> **Comments:**
> **username_1**: Using the Ajtai–Komlós–Szemerédi sorting network, you can *completely* sort the array using $O(\log n)$ comparisons per element.  
> **username_2**: There is also a question for [sorting without an AKS network](https://cstheory.stackexchange.com/q/7131)  
> **username_0**: @japh Thanks, thats exactly what I was looking for. Something which doesnt use networks.  

---

## 0 answers

