Solution: One Array at a Time

The obvious plan is to keep a running result. This will not meet the target time complexity. Let’s see why.

Start with an empty array, merge the first input into it, merge the second input into that, and so on. Each step is the two-array merge from the chapter.

Let’s set up the loop first:

public static int[] mergeAll(int[][] arrays) {
  int[] result = new int[0];
  for (int i = 0; i < arrays.length; i++) {
    // fold arrays[i] into result
  }
  return result;
}

result starts empty, which is a sorted array with nothing in it. Each pass through the loop should leave result sorted and holding every element of the arrays we have seen so far. The merge gives us exactly that. It takes two sorted arrays and returns a new sorted array with the elements of both:

public static int[] mergeAll(int[][] arrays) {
  int[] result = new int[0];
  for (int i = 0; i < arrays.length; i++) {
    result = merge(result, arrays[i]);
  }
  return result;
}

Here merge is the first merge from the chapter, the one that returns a new array.

Does this handle the edge cases correctly?

• If arrays has length 0, the loop never runs and the empty result comes back.
• If arrays holds a single array, the one merge is of an empty array with that array, which gives a copy of it.
• If some input array is empty, its merge copies result and adds nothing. The chapter’s merge handles an empty input because its loop runs over the output, and the exhausted-array checks take everything from the other array.

Let’s trace it on the four arrays from the problem. The running result is on the left:

[]                      + [1, 8]  ->  [1, 8]                     2 copies
[1, 8]                  + [3, 5]  ->  [1, 3, 5, 8]               4 copies
[1, 3, 5, 8]            + [2, 9]  ->  [1, 2, 3, 5, 8, 9]         6 copies
[1, 2, 3, 5, 8, 9]      + [4, 7]  ->  [1, 2, 3, 4, 5, 7, 8, 9]   8 copies

The answer is right. Look at the copies, though. The 1 and the 8 were copied four times, once per merge. The 4 and the 7 were copied once. An element merged early is copied again in every later merge.

What does this cost? A two-array merge costs one copy per element in its output. Say the $k$ arrays have $m$ elements each, so $n=km$. The merges produce results of $m,2m,3m,\dots ,km$ elements, for a total of

$$m(1+2+\cdots +k)=m\cdot \frac{k(k+1)}{2}\approx \frac{nk}{2}$$

That is $O(nk)$. When the arrays have different lengths the count changes, but the bound does not. The merge in step $i$ copies everything merged so far, and there are $k$ steps.

For two arrays this is just the merge, $O(n)$. For $k=n$ arrays of one element each it is $O(n^2)$, the cost of insertion sort. Inserting one element at a time into a sorted result is what insertion sort does.

The auxiliary space is $O(n)$. At any moment there is the old result and the new one merge is building, and neither is longer than $n$.