Can be done in O(n) time but it will need O(n) space too
take another array of same length
then its code will be
for( i=0,j=0,k=n/2+1 ;i<=n/2&&k<n; )
{
if(arr[i]>arr[k])
new[j++]=arr[k++];
else
new[j++]=arr[i++];
}
if(k<n)
{
while(i<=n/2)
new[j++]=arr[i++]
}
else
{
while(j<n)
new[j++]=arr[k++]
}
On Fri, Aug 19, 2011 at 12:40 AM, *$* <[email protected]> wrote:
> Sort an array of n positive integers containing n/2 sorted integers in
> first and second-half?
> in O(n) time complexity ..
> and space complexity should be constant
>
>
> --
> 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.
>
--
**Regards
SAGAR PAREEK
COMPUTER SCIENCE AND ENGINEERING
NIT ALLAHABAD
--
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.
