In case if you need in place merging than you need to use bi- tonic merge. But the only condition is total array length should be power of two.
http://codepad.org/hG8CnM1l On Mon, Jul 12, 2010 at 11:13 AM, srikanth sg <[email protected]>wrote: > u are using extra memory which is not supposed to be done.. > > On Mon, Jul 12, 2010 at 10:56 AM, Anand <[email protected]> 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 <[email protected]>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 <[email protected]> >>> Date: Mon, Jul 12, 2010 at 8:18 PM >>> Subject: [algogeeks] Re: sort in O(n) >>> To: Algorithm Geeks <[email protected]> >>> >>> >>> 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 [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]<algogeeks%[email protected]> >>> . >>> 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 [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]<algogeeks%[email protected]> >>> . >>> 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 [email protected]. >> To unsubscribe from this group, send email to >> [email protected]<algogeeks%[email protected]> >> . >> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > 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 [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.
