Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Quicksort/Insertion sort combo

  1. Oct 10, 2008 #1
    1. The problem statement, all variables and given/known data
    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?

    3. 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!
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted