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.
