2
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ Using the Ajtai–Komlós–Szemerédi sorting network, you can completely sort the array using $O(\log n)$ comparisons per element. $\endgroup$
    – Emil Jeřábek
    Commented Sep 22, 2019 at 7:12
  • 2
    $\begingroup$ There is also a question for sorting without an AKS network $\endgroup$
    – japh
    Commented Sep 23, 2019 at 7:56
  • $\begingroup$ @japh Thanks, thats exactly what I was looking for. Something which doesnt use networks. $\endgroup$
    – Vk1
    Commented Oct 5, 2019 at 5:41

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.