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!


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.