One idea is to simply concatenate the arrays and then call sort. That's an $O( n \log n)$ algorithm. However, we can do much better than that. An indication that we can do better that this is that the concatenate algorithm doesn't take advantage of the fact that the k arrays are sorted at all.

The optimal idea is to add all the elements to a larger array in increasing order:

To find the smallest element, we just have to consider the leftmost elements in all the arrays, because they're all sorted. We can take the min of all the leftmost numbers to get the smallest number.

We can keep taking the min over the leftmost numbers to get the next number in the array.

Many of the same numbers show up whenever we take the min. This means we should use a Heap data structure to optimize, so that taking the min is fast.

The algorithm is to put all the leftmost values into a Heap. You then pop the heap to get the min of all the values. You also have to replace the value that you removed from the Heap. By iterating this, you end up with a big sorted array.

Here's the code for this:

Time Complexity $O(n \log k)$. We pop the heap whenever we add a new element to the array. There are $k$ elements in the Heap, and the heap is a balanced tree, so this takes $O(\log k)$ time. We do this for all the $n$ elements. This gives $n*O(\log k) = O(n \log k)$ time.

Space Complexity $O(n)$. The Heap requires $O(k)$ space, and the solution array requires $O(n)$. This is just $O(k)+O(n) = O(k+n) = O(n)$ since n is always larger than k.

Note: naively calling sort has $O(n \log n)$ time complexity. This means the heap solution is always better, since it's always true that $k \le n$.