K-way merge algorithm

Sequence Merge Algorithms are a family of algorithms that run sequentially over multiple sorted lists, typically producing more sorted lists as output. K-Way Merge Algorithms are the class of merge algorithms that take as input a group of more than one sorted lists, and output a single sorted list.

Assume that we are given a group of sorted lists S that we want to merge into a single sorted list.

Optimal 2-Way Merge

2-Way Merge has been studied extensively as a part of Merge sort. It would be trivial to simply walk through S and merge together two sorted lists at a time using the merge function found in Merge sort, until only one final list is left. The question then becomes how to find the optimal merge pattern.

An example of Huffman Coding, which uses the same technique as in the optimal merge. The values shown would represent each list length.

The optimal merge pattern is found by utilizing a Greedy algorithm that selects the two shortest lists to merge. This technique is similar to the one used in Huffman coding.