Given an integer array of which both first half and second half are
sorted. Write a function to merge the two parts to create one single
sorted array in place [do not use any extra space].
e.g. If input array is [1,3,6,8,-5,-2,3,8] It should be converted to:
[-5,-2,1,3,3,6,8,8]
i have thought of the following approach
[1,3,6,8,-5,-2,3,8]
| |
ptr1 ptr2
*ptr1<*ptr2
so shift as follows
[ -5,1,3,6,8,-2,3,8]
| |
ptr1 ptr2
[-5,-2,1,3,,6,8,3,8]
| |
ptr1 ptr2
[-5,-2,1,3,6,8,3,8]
| |
ptr1 ptr2
[-5,-2,1,3,6,8,3,8]
| |
ptr1 ptr2
[-5,-2,1,3,3,6,8,8]
| |
ptr1 ptr2
[-5,-2,1,3,3,6,8,8]
| |
ptr1 ptr2
{-5,-2,1,3,3,6,8,8]
but i think there must be some O(n) algo for this..
--
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.
