The solution could be given in this way.
1) In one pass get the end index of both array says e1 and e2.
2) now in next pass compare elements at e1 and e2 .
a) if a(e1) > a(e2) swap the elements and then decreament e1 and e2 both.
b) if a(e1) < a(e2) decreament e2.
c) if a(e1) == a(e2) then swap a(e1) with a(e2-1) and then decrement e1
by1 and e2 by 2.
After this pass there may be one or two element not at coret position, so
their position can be placed just by shifting in elements in another pass.
So as a total it would be O(n) but it requires 3 passes.
If some one is having something better tan this, please suggest.
On Sun, May 26, 2013 at 6:46 PM, bharat b <bagana.bharatku...@gmail.com>wrote:
> An array is given, first and second half are sorted .. Make the array
> sorted inplace... Need an algo better than O(n^2)..
> If the length of the array is odd.. middle is either in first half or
> second half.
> Ex:
> 1. Arr[] = {2,3,6,8,-5,-2,3,8} --> output : Arr[]={-5,-2,2,3,3,6,8,8};
> 2. Arr[] = {2,3,6,8,-5,-2,3} --> output : Arr[]={-5,-2,2,3,3,6,8};
> 3. Arr[] ={2,3,6,-5,-2,3,8} --> output : Arr[]={-5,-2,2,3,3,6,8};
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
>
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
