@ankit
it can be done without shifting elements
On Fri, Jul 8, 2011 at 9:52 AM, ankit sambyal <ankitsamb...@gmail.com>wrote:
> Algo :
> Given array a[m] and b[2*m]
>
> 1. Shift the elements in the array b to the right half. Now the m
> elements in the array b are from index m to 2m-1
> 2. Initialize i (iterator of array a[]) =0
> j (iterator of array b[]) = m
> k (iterator of the final array which is b[]) = 0
> 3.
> while(1)
> {
> if(i==m)
> break;
> else if(j==2m)
> {
> Copy the remaining elements from array a[] into array b[]
> Then break;
> }
> else
> {
> if(a[i] < b[j])
> b[k++]=a[i++];
> else
> b[k++]=b[j++];
> }
> }
>
>
> Time Complexity : O(m)
> Space Complexity : O(1)
>
>
> On Thu, Jul 7, 2011 at 1:49 PM, sunny agrawal <sunny816.i...@gmail.com>
> wrote:
> > O(m) is always better than O(m^2) :) :P
> > Simple merge sort
> > hint : start from end of the arrays
> >
> > select the text in white font to see the hint :)
> >
> > On Fri, Jul 8, 2011 at 1:56 AM, Dumanshu <duman...@gmail.com> wrote:
> >>
> >> given two sorted arrays a[m] b[2*m], each contains m elements only.
> >> You
> >> need to merge those two arrays into second array b[2*m].
> >> anything better than O(m^2)????
> >>
> >> --
> >> 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.
> >>
> >
> >
> >
> > --
> > 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.
> >
>
> --
> 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.
>
>
--
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.
