u are using extra memory which is not supposed to be done.. On Mon, Jul 12, 2010 at 10:56 AM, Anand <anandut2...@gmail.com> wrote:
> @amit: according to your given example this how the logic works. > > In the below code I took an array a[]={1,9,10,2,4,6}; in the example at the > mid point second array start so mid point logic works here. but according to > given question we can scan through the array once and can find out where > actually the array start decreasing which is starting point of the second > array. > > Complexity of merge the array is O(n). > > http://codepad.org/PCoswp0c > > > > > On Mon, Jul 12, 2010 at 8:06 AM, Amit Jaspal <amitjaspal...@gmail.com>wrote: > >> @ above can u please be more specific >> >> let A[1,9,10] and B [2,4,6] >> >> Now how to swap so that the complexity remains O(n) >> >> >> ---------- Forwarded message ---------- >> From: Tech Id <tech.login....@gmail.com> >> Date: Mon, Jul 12, 2010 at 8:18 PM >> Subject: [algogeeks] Re: sort in O(n) >> To: Algorithm Geeks <algogeeks@googlegroups.com> >> >> >> 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<algogeeks%2bunsubscr...@googlegroups.com> >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> >> >> >> >> -- >> Amit Jaspal >> Btech IT IIIT- Allahabad >> >> >> -- >> 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<algogeeks%2bunsubscr...@googlegroups.com> >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- > 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<algogeeks%2bunsubscr...@googlegroups.com> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- 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.