Solution: Merging in Pairs

The one-at-a-time plan copies early elements over and over because every merge includes everything merged so far. Merge sort would have the same problem, but it avoids it. It never merges a big run with a small one. It merges runs of about the same size, so each element takes part in one merge per level, and there are only $lo g_{2} n$ levels.

Let’s do the same with the $k$ arrays. Split the list of arrays in half. Merge the left half into one sorted array, merge the right half into one sorted array, then merge those two. “Merge the left half” is the same problem on fewer arrays, so it is a recursive call. That means we need a helper that works on a range of arrays, from start up to but not including end:

private static int[] mergeAll(int[][] arrays, int start, int end) {
  // merge arrays[start..end-1] into one sorted array
}

The base case is a range of one array, which needs no merging, so we return it as it is. Otherwise we split at the middle, recurse on both halves, and merge the two results:

private static int[] mergeAll(int[][] arrays, int start, int end) {
  if (end - start == 1) {
    return arrays[start];
  }
  int mid = start + (end - start) / 2;
  int[] left = mergeAll(arrays, start, mid);   // merge the left half
  int[] right = mergeAll(arrays, mid, end);    // merge the right half
  return merge(left, right);                   // merge the two results
}

The public method starts the recursion over the whole range. The helper’s base case assumes the range holds at least one array, so the public method has to handle the empty case itself:

public static int[] mergeAll(int[][] arrays) {
  if (arrays.length == 0) {
    return new int[0];
  }
  return mergeAll(arrays, 0, arrays.length);
}

This is recursive merge sort with one change. Merge sort’s base case is a range of at most one element, which is sorted because there is nothing to order. Here the base case is a range of one array, which is sorted because the problem says so. Everything above the base case is the same.

The base case returns the input array itself rather than a copy. That is fine here, because merge always builds a new array, so no caller ever writes into an input. With $k = 1$ , though, the public method returns the single input array to the caller. If the caller might modify the returned array, return a copy of it instead.

Let’s trace it on the four arrays from the problem:

mergeAll(arrays, 0, 4)
  mergeAll(arrays, 0, 2)
    mergeAll(arrays, 0, 1)  ->  [1, 8]
    mergeAll(arrays, 1, 2)  ->  [3, 5]
    merge                   ->  [1, 3, 5, 8]                    4 copies
  mergeAll(arrays, 2, 4)
    mergeAll(arrays, 2, 3)  ->  [2, 9]
    mergeAll(arrays, 3, 4)  ->  [4, 7]
    merge                   ->  [2, 4, 7, 9]                    4 copies
  merge                     ->  [1, 2, 3, 4, 5, 7, 8, 9]        8 copies

That is sixteen copies, compared with twenty for the one-at-a-time plan. The gap is small because $k$ is small. Every element was copied exactly twice here, once per level of the recursion, and $2 = lo g_{2} 4$ .

Does this handle the edge cases correctly?

If arrays has length 0, the public method returns an empty array before the recursion starts.
If arrays holds a single array, the helper hits its base case at once and returns that array.
If some input array is empty, it reaches a base case like any other and is merged as an empty input, which the chapter’s merge handles.
If $k$ is not a power of two, the halves are uneven, just as in merge sort on an array of any length. Every range still shrinks, and every range of one array stops.

What does this cost? The recursion tree has the arrays at the leaves and a merge at every other node. As in merge sort, the merges at one level together copy every element once, which is $O (n)$ . There are $lo g_{2} k$ levels, because that is how many times $k$ arrays can be halved down to one. So the total is $O (n lo g k)$ .

Compare that with $O (nk)$ for merging one at a time. For $k = 2$ both are just the merge. For $k = n$ single-element arrays, pairwise merging is $O (n lo g n)$ , which is merge sort’s cost, and merging one at a time is $O (n^{2})$ , which is insertion sort’s cost.

The auxiliary space is $O (n)$ . On the way up, a call holds left and right while merge builds the merged array, and those three together never exceed $2 n$ . The call stack adds $lo g_{2} k$ frames, which is smaller than $n$ . Recursive merge sort’s analysis had the same two terms.