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! -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
