The running time of quicksort can be improved in practice by taking advantage of the fastrunning time of insertion sort when its input is “nearly” sorted. When quicksort is called on asubarray with fewer than k elements, let it simply return without sorting the subarray. After thetop-level call to quicksort returns, run insertion sort on the entire array to finish the sorting process.