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