Problem: Merge k Sorted Arrays

Let’s look at a classic problem that reuses the merge: merging more than two sorted arrays.

Take these four arrays:

arrays[0]:  [1, 8]
arrays[1]:  [3, 5]
arrays[2]:  [2, 9]
arrays[3]:  [4, 7]

The result is [1, 2, 3, 4, 5, 7, 8, 9]. Each input array is sorted on its own, but there is no order across the arrays. The 2 in the third array comes before the 3 in the second.

The arrays do not have to be the same length. Duplicate values may appear, within an array or across arrays, and every copy belongs in the output. So merging [1, 4], [4], and [2, 4] gives [1, 2, 4, 4, 4].

The signature of the method in Java might look like this:

public static int[] mergeAll(int[][] arrays) {
  // Your implementation goes here
}

You already have a merge of two sorted arrays. The question is how to use it to combine $k$ of them. Any way you do it, you will call the two-array merge $k - 1$ times. What matters is which arrays you merge together, and in what order.

Let’s think of some special or edge cases as well:

If arrays has length 0, there is nothing to merge, and the result is an empty array.
If arrays holds a single array, the result holds the same elements as that array.
If some input array is empty, it contributes nothing, and the merge has to handle an empty input.
If every input array is empty, the result is an empty array.

Let $n$ be the total number of elements across all $k$ arrays. The solution must run in $O (n lo g k)$ time.