Cormen Edition 3 Exercise 7.4 Question 5 (Page No. 185)

Question

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+n\ lg\ (n/k))$ expected time. How should we pick $k$, both in theory and in practice?

Answer 1

 

this might help