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 + n lg n/ k)$ expected time. How should we pick k, both in theory and in practice? Quick-sort should run until we have k elements. $$n/2^i = k $$ Applying log $$i = log n/k $$ the height of the tree is $log n/k$ The time partition procedure runs is $O(n)$ and for a height of log n/k the running time for quick sort is $O(n log n/k)$ Now we have n/k sub arrays with each k unsorted elements the time for insertion sort is $$O(n/k . k^2)$$ $$O(n.k)$$ The expected running time is $O(nk + n lg n/ k)$. We should pick k as log n so the running time is n log n which is the best expected running time. In practice we pick k such that its values is around log n and provides better performance than quick-sort.