@abv amit askd inplace merging
On Mon, Jul 12, 2010 at 11:26 PM, 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.
>
--
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH 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.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
