title: Running time of sorting with a black-box findmax subroutine
body: <p>Suppose you had a black-box subroutine that could extract the max from an array of n elements in <code>(log n)^a</code> time, where <code>0 &lt;= a &lt;= 1</code>. You're trying to create an optimal sorting algorithm that makes use of this subroutine.</p>
  
  <p>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 <code>A[1, n-1]</code> through <code>A[1, 2]</code>.</p>
  
  <p>Is there a better algorithm that runs faster than <code>n*(log n)^a</code> time, or is the obvious solution optimal?</p>