i dont know O(n) but here is an O(nlgn) algorithm
reverse the second half, the final sequence obtained will be a bitonic
sequence
to sort a bitonic sequence
compare i with i+n/2,put smaller in first half and larger in other
finally you will get 2 bitonic sequences, 0->n/2 ans n/2+1 ->n
so do recurcively for them
On Sat, Jan 22, 2011 at 12:21 PM, snehal jain <learner....@gmail.com> wrote:
> Given an integer array of which both first half and second half are
> sorted. Write a function to merge the two parts to create one single
> sorted array in place [do not use any extra space].
> e.g. If input array is [1,3,6,8,-5,-2,3,8] It should be converted to:
> [-5,-2,1,3,3,6,8,8]
>
> i have thought of the following approach
> [1,3,6,8,-5,-2,3,8]
> | |
> ptr1 ptr2
>
> *ptr1<*ptr2
> so shift as follows
> [ -5,1,3,6,8,-2,3,8]
> | |
> ptr1 ptr2
> [-5,-2,1,3,,6,8,3,8]
> | |
> ptr1 ptr2
> [-5,-2,1,3,6,8,3,8]
> | |
> ptr1 ptr2
> [-5,-2,1,3,6,8,3,8]
> | |
> ptr1 ptr2
> [-5,-2,1,3,3,6,8,8]
> | |
> ptr1 ptr2
> [-5,-2,1,3,3,6,8,8]
> | |
> ptr1 ptr2
> {-5,-2,1,3,3,6,8,8]
>
>
> but i think there must be some O(n) algo for this..
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@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.
>
>
--
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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.
