k-way merge with divide and conquer?

Question

The idea is to recursively merge the first k/2 lists and the second k/2 lists, then merge the two merged lists into one list and return.

I'm confused on what it means to recursively merge the first k/2 with the second k/2 lists. Can anyone clarify this or maybe go over some pseudo code that explains this recursion?

Answer 1

List recursiveMerge(List[] lists)
{
  // Easy to solve problem for up to length 2
  if (lists.length < 1)
  {
    return new List();
  }
  if (lists.length == 1)
  {
    return lists[0];
  }
  if (lists.length == 2)
  {
    return baseMerge(lists[0], lists[1]);
  }
  // For longer lengths split the array into two
  int half = lists.length / 2;
  List[] firstHalf = new List[half];
  List[] secondHalf = new List[lists.length - half];
  System.arraycopy(lists, 0, firstHalf, 0, firstHalf.length);
  System.arraycopy(lists, firstHalf.length, secondHalf,
    0, secondHalf.length);
  // Solve the problem separately in each sub-array
  List a = recursiveMerge(firstHalf);
  List b = recursiveMerge(secondHalf);
  // and produce a combined solution
  return baseMerge(a, b);
}

If you start with N lists 0,1,2,3... then at the bottom of the recursion tree we merge 0 with 1, 2 with 3, 4 with 5, and so on. The next step merges 0+1 with 2+3, 4+5 with 6+7, and so on. So if there are N lists there are lg(N) levels in the tree, each of which processes each data point once. So if there are N lists of total length L the cost is O(L log(N)).