CareerCup

take every two adjacent sorted arrays, merge them in place say the initial sorted arrays are X1 X2 X3 ...XN.
we merge X1 and X2 in place keeping the result in array which is indexed from X1[0] to
X2 [2N-1] similarly for the next two arrays. after the first pass we have m/2 sorted arrays of length 2n each . in the next pass we shall consider sorted arrays of size double the previous pass.
every pass takes m*n time and we have logm no. of passes.total time complexity is O(mnlogm)

store elements in binary search tree and do IN order

1. Maintain a heap of size m (number of arrays) .
2. Create a min heap containing first elements of all m arrays.
3. Pull the root node from the heap. This is the smallest element.
4. Add to the heap, the second node of the array to which this number belongs to.
5. Heapify the modified heap
6. Repeat step 2 to 6 until all elements are processed.

Algorithm complexity - O(log(mn))

This is the Mergesort Merge Function Call.

In place merge sort might be the answer. In reality In place merge sort is hard to get right the easier solution is Quicksort.

Assuming the output array's space is availabe.. make a heap of all the arrays and heapsort. Better then O(n^2) by merging individually..