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 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.