Suppose you had a black-box subroutine that could extract the max from an array of n elements in (log n)^a time, where 0 <= a <= 1. You're trying to create an optimal sorting algorithm that makes use of this subroutine.
The obvious solution is to call the subroutine on the entire array, swap the max with the last element, and then call the sub-routine iteratively on A[1, n-1] through A[1, 2].
Is there a better algorithm that runs faster than n*(log n)^a time, or is the obvious solution optimal?