Improving quicksort by implementing insertion sort [closed]

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center. Closed 11 years ago.

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 algorit开发者_运维问答hm runs in O(nk + n log (n/k)) expected time. How should k be picked, both in theory and in practice?

---

Roughly speaking:

quicksort is O(N log(N))

By stopping when the sub-lists are of length k, the quicksort part becomes O(N log(N/K)) because the depth you have to go to is reduced by a factor of K.

The insertion sort would normally be O(n^2) because you move each element at most n/2 times on average, and the factor of 1/2 is ignored.

Because the insertion sort is now on a fixed length array, you only move each element at most k places. This results in the insertion sort part of your operation being O(NK).

In theory, larger values of K give faster sorts, but that relies on the number of items being sorted being large. In practise, the best value of k will depend on the value of n and can be found by differentiating the function in terms of k treating n as a constant.

This answer will probably need some fleshing out and formal proof if it is a homework question as Delan suggests.