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.

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

Your Answer

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

Browse other questions tagged or ask your own question.