Coarsening the recursion, as we did in Problem $2-1$ for merge sort, is a

common way to improve the running time of quicksort in practice. We

modify the base case of the recursion so that if the array has fewer than

k elements, the subarray is sorted by insertion sort, rather than by

continued recursive calls to quicksort. Argue that the randomized

version of this sorting algorithm runs in O$($nk $+$ n lg$($n$/$k$))$ expected

time. How should you pick k$,$ both in theory and in practice?