If all you need to do is print what the result of the merge would be then sure, a solution does exist.
The basic idea is to use the (unused) beginning of array b as swap space for the beginning of array a. This swap space needs to be shifted around, so it's of course O(n^2). Still, it was fun to write.
If you have termcolor installed ('sudo easy_install termcolor' on ubuntu), you'll see the arrays a and b as well as the swap space highlighted in color for each step. Example: http://dl.dropbox.com/u/2135523/2013022517.png
I wasn't saying you can't sort arrays in place (quicksort). I was saying you can't merge them in place. Somebody has to grow.
For any practical purpose that's as good as a contiguous array, and in embedded systems you might even make so that the initial two arrays are already contiguous in memory.
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.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.
Ok, any real-world usage might be applicable only in embedded systems which is a fairly narrow domain.
Still, it is a small (easy to describe) problem that can be used to see how the applicant does problem solving for problems without a widely known best/proper solution - and that skill is probably 90% of any serious programming; the remainder is just typing while following an arbitrary syntax which a trained monkey can do.
And the solution definitely exists - depending on how the interviewer wants output, you can either push the result out with a trivial iteration with a pointer on each array; or if the arrays aren't read only, you can sort them in-place with a slightly modified qsort or even bubblesort - both of these approaches don't need to allocate any memory on the heap, just 2 int counters in processor registers or stack.