JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat  | Threaded  | Tree
Previous Thread  |  Next Thread
Regarding Merge Sort | Reply
Running time of merge sort is O(nlgn)and i am continuosly breaking my array into smaller sub arrays,what if I stop this recursive procedure upto some depth(of the recurrence tree) and then individually apply insertion sort on those sub arrays.Let us assume we got k sublists and total number of numbers in each of these sublists will be n/k, running time will be greatly reduced(as compared to normal procedure of merge sort) if these k sublists are already sorted.But how to choose this value of k so that we can generate efficient code?
Re: Regarding Merge Sort (response to post by cnitin_ice) | Reply
I guess you run some code and test what works the best. In Java they decided 7 was the limit (if (length < 7) do insertion sort). I don't know if that can be improved or not.
Re: Regarding Merge Sort (response to post by cnitin_ice) | Reply
If you cut on the number of sublists rather than the length of the sublists, your algorithm will be O(n^2) instead of O(n log n).
Re: Regarding Merge Sort (response to post by cnitin_ice) | Reply
You can try a ternary search on k :-)

Realistically, k is small enough (~7) that you don't need to do that. But supposing that you didn't already know this, and this appeared as a TC problem, that's what I'd do! :-)
Re: Regarding Merge Sort (response to post by cnitin_ice) | Reply
You'll probably be interested in reading about "introsort" or "introspective sort".
RSS