On Jul 12, 10:48 am, Tech Id <[email protected]> wrote: > This is a good solution. > > Reversing the arrays will be O(n) > Then merging will be O(n) too. > > In place merge is something like this. > Have two indices as start1 and start2 > start1 points to beginning of mini-sorted portion1 > start2 points to beginning of mini-sorted portion2 > > Increase both start1 and start2 and swap when necessary. > adjust start1 and start2 accordingly. > > Do the same for other mini-sorted arrays. > > So the complexity of this is mO(n) where m is the number of mini > arrays. > For m=1, it becomes O(n^2) as expected for a normal sort!
Correct algorithms for in-place merge are much harder than what you're describing here. Think it through carefully, and you'll see this. And don't forget that if you are merging K lists, you need at least K log K comparisons to decide the merge order at each step. So if the lists being merged have about N items each, the cost of merging is O(N K log K) . In other words, the "K" in K-tonic makes a difference. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
