0
$\begingroup$

excuse me for the long title. My goal is to find an algorithm to sort an array of n elements, with an oracle, which must be used O(logn) times.
Given a partition of our array (resulting in two subsets, A and B), this oracle can tell us how many elements in B are smaller than a given element in A in O(1).
A naive approach would be partitioning the array to an element and a subarray of n-1 elements, and using the oracle to determine the position of our single element. Doing this n times would sort the array in O(n).
However I cannot think of any algorithm that would perform better than O(n), and I am beginning to question whether or not this is possible?
thanks in advance!

$\endgroup$

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.