1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you help with the solution or looking for help too?

Similar Discussions: Quicksort/Insertion sort combo
  1. Merging sorted lists (Replies: 0)