# Sorting with a recursive oracle

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})$.
• 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. – Erel Segal-Halevi Oct 20 '14 at 18:15