@ankit
it can be done without shifting elements
On Fri, Jul 8, 2011 at 9:52 AM, ankit sambyal <[email protected]>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 <[email protected]>
> 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 <[email protected]> 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 [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.
> >>
> >
> >
> >
> > --
> > 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 [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.
> >
>
> --
> 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.
>
>
--
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 [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.
