Few things I would do before actually starting up. Assuming A is the n length array, B is the 2n length array, and the elements in B start at 0 to n-1. If A[n-1] < B[0] Then move all the elements in B to the end of the array and copy A to the beginning of B. If B[n-1] < A[0] do the opposite of above If none of these apply, move up from B[0] to B[n] looking for when B[x] is higher than A[x]... do more stuff like this to have to avoid using Mergesort or any other sort that relies on a completely unsorted array. Use the information given to you and the restrictions put on the data to come up with speed increasing special cases.

Here is the Python implementation: def m(A, B): c1 = len(e1)-1 c2 = 2*len(e1)-1 while(c2 > c1): B[c2] = max(A[c1], B[c1]) B[c2-1] = min(A[c1], B[c1]) c1 -= 1 c2 -= 2

#include using namespace std; int main() { int a[]={2,3,4,7}; int b[8]= {3,5,6,8}; int i1= 3,i2 =3,k =7,i; while(k) { if(i1 =0 ; i--) b[k--] = b[i]; k = 0; } else if (i2 =0 ; i--) b[k--] = a[i]; k =0; } else if (a[i1] >b[i2]) { b[k--] = a[i1]; i1--; } else { b[k--] = b[i2]; i2--; } } for(i=0; i< 8; i++) cout<

Two cases: a) 2n array elements start from 0. b) 2n array elements start from n/2. Cases are symetric to each other. IMHO, the most beatiful answer to this question is to use the linked-list cycle detection concept where we have two pointers one is incrementing one and other is incrementing two. If those match then we have a cycle. In this example, if the case A is correct we can do following: # Let A be n array, and B is 2n array c1 = n-1 c2 = 2n-1 while(c2 > c1): if A[c1] > B[c1]: B[c2-1] = B[c1] B[c2] = A[c1] else: B[c2-1] = A[c1] B[c2] = B[c1] c1 -= 1 c2 -= 2 Implementation may have more specific details but the idea is obvious.