Can you partially sort using $O(\log n)$ comparisons per element?

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.

• 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 Sep 22 '19 at 7:12
• There is also a question for sorting without an AKS network – japh Sep 23 '19 at 7:56
• @japh Thanks, thats exactly what I was looking for. Something which doesnt use networks. – Vk1 Oct 5 '19 at 5:41