Its the same as we do merge sort where we merge the two sorted array into
one which will require an extra array......
Is there any algorithm for inplace mergesort...?
On Fri, Aug 19, 2011 at 2:09 PM, sagar pareek <sagarpar...@gmail.com> wrote:
> 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, *$* <gopi.komand...@gmail.com> 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 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.
>>
>
>
>
> --
> **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 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.
>
--
Abhishek Yadav
Comp Engg.
NIT Kurukshetra
--
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.
