- #1
flash
- 68
- 0
Homework Statement
The running time of quick sort can be improved in practice by taking advantage of the fast running time of insertion sort when its input is nearly sorted.
When quicksort is called 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 log (n/k)) expected time. How should k be picked, both in theory and in practice?
The Attempt at a Solution
I have done the first part and shown that the running time is as given. I have no idea how to go about the second part, however. I know the answer should be around 20 or so, this is given without proof in the text. I tried to minimise the O function for k which gives k = 1/log2 which is obviously not right. Any help appreciated!