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].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
