[kramarao]

This is standard undergraduate question in algorithms when I went to college. If you need N log(N) solution, look up in-situ mergesort. If you don't care about the order of algorithm, there are much simpler intuitive ways of doing it.

Assume that you have two sorted arrays A and B. At the end of it, A followed by B needs to be sorted. Here is a simple algorithm:

Sort(A,B):

    if A[0] is greater than B[0], swap A[0] and B[0]. 
        Bubble up B[0] to its right place (that is make B sorted).

   Sort(A+1, B) -- stop if A reached its end.

Naive implementation, such as this is N^2. Leaving it to readers to make it N log(N), which is actually trivial.

That comes to a different point. When I was going to college in Computer science, we had to go through at least three courses in algorithms. We used to hand code most algorithms optimizing for the situation at hand. I suppose the advent of good libraries, and the bottlenecks elsewhere in the systems means that this generation may not find fundamentals of algorithms much use. Instead, they may find concepts in abstraction, higher order functions etc more useful.