Multi-Way Merge
March 29, 2016
A multi-way merge takes two or more sorted input lists and creates a single output list that contains all the elements of the various input lists in sorted order.
If there are only two input lists, this is easy; run through the lists in order, at each step moving the smaller of the two elements at the heads of the lists to the output.
Things get harder if there are k input lists with k > 2. The easiest approach is to merge the first two lists, then merge that with the third list, and so on, performing k − 1 merges.
The “tournament” approach first merges input lists pairwise, forming a new set of k / 2 lists each twice as long as the originals, then recurs. Thus input lists 1 and 2 are merged, then 3 and 4 are merged, and so on, then merged list 1/2 is merged with merged list 3/4, and so on, until at the end only one merged list remains.
The best approach is to arrange all the input lists in a priority queue based on their smallest element. At each step the element at the head of the priority queue is written to the output, that element is removed from the list at the head of the priority queue, and the priority queue is reformed to put the new smallest element at its head.
Your task is to write the three versions of multi-way merge described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
Not directly on point, but Olin Shivers’s list merge sorts for SRFI 32 definitely repay study. Both are natural (preserve order) and stable. The destructive version doesn’t allocate any new pairs, it just set-cdr’s everything into shape.
Nice exercise in linked-list bashing. Here’s the tournament sort but arranged to recurse down each half of the list before merging the two results, comes to much the same thing, but maybe has better locality. C++ but only just:
struct Node { Node(int n_,Node *next_): n(n_), next(next_) {} int n; Node *next; }; // a is an array of n Node * lists. Node *merge(Node **a, int n) { if (n == 1) return *a; Node *p = merge(a,n/2), *q = merge(a+n/2,n-n/2); Node *r = NULL, **t = &r; while(p && q) { if (p->n <= q->n) { *t = p; t = &p->next; p = *t; } else { *t = q; t = &q->next; q = *t; } } if (p) *t = p; else if (q) *t = q; return r; }