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