It is known that the runtime complexity of sorting is $\Theta (n \log n)$. But what if we have, for every input array of size $n$, an oracle that can sort any array of $k<n$ numbers in constant time?

In this case, the runtime of merge sort becomes $O(n)$. The recursive calls are cheap and the runtime is dominated by the merging step.

Does there exist a more efficient algorithm for sorting, using these oracles? My guess is that the answer is negative, i.e. sorting with recursive oracles has runtime complexity $\Theta(n)$. Is this correct?

NOTE: this is a special case of the following question from cstheory.SE L https://cstheory.stackexchange.com/questions/27094/are-there-problems-for-which-divide-and-conquer-is-provably-useless


If you can sort arrays of size $n-1$ then three recursive applications of this sorting procedure are enough, say prefix, suffix, prefix. You can see that using the zero-one sorting theorem, which states that a sorting algorithm works if it can sort zero-one inputs. I leave the case analysis to you.

This algorithm probably works for much smaller $k$. Moreover, it should be the case that given a sorting oracle for $k=cn$ you can sort in $O_c(1) $ time. One can even guess a formula, $O(c^{-1} \log c^{-1}) $.

| cite | improve this answer | |
  • $\begingroup$ If all you need is to sort an array of zeros and ones, then why not use a single recursive call? Sort the first $n-1$ elements, then check the $n$-th element: if it is 0, send it to the beginning of the array, if it is 1, send it to the end. $\endgroup$ – Erel Segal-Halevi Oct 20 '14 at 18:15
  • $\begingroup$ The zero-one theorem holds only for comparator networks. In particular, the only thing you're allowed to do is to take two elements and sort them. In the analysis you only need to consider zero-one inputs. $\endgroup$ – Yuval Filmus Oct 20 '14 at 18:29

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.