I am self learning CLRS 3rd edition and here is one of the tougher questions that I have encountered along with its answer as a service to all.
7.4-5
We can improve the running time of quicksort in practice by taking advantage of the
fast running time of insertion sort when its input is “nearly” sorted. Upon calling
quicksort on a subarray with fewer than k elements, let it simply return without
sorting the subarray. After the top-level call to quicksort returns, run insertion sort
on the entire array to finish the sorting process. Argue that this sorting algorithm
runs in O(nk+nlg(n/k)) expected time. How should we pick k, both in theory
and in practice?
If you eval equation nlgn > nk + nlog(n/k) you get log k > k. Which is impossible. Hence in theory it's not possible. But in practice there are constant factors involved with insertion sort and quicksort. Take a look at the solution discussed in this pdf. You might want to update your answer. .