Upon running quicksort on a subarray with fewer than k elements, it returns without sorting subarray. After top level call to quicksort returns, insertion sort is run on entire array to finish sorting. Then the sorting algo runs in:
O(n lg(n/k) ) O(n+ n lg(n/k)) O(nk + n lg(n/k)) none