JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Tutorial Discussions Sorting Tutorial Regarding Merge Sort
 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".
 Forums Tutorial Discussions Sorting Tutorial Regarding Merge Sort Previous Thread  |  Next Thread