K-way merge algorithm

This sandbox is in the article namespace. Either move this page into your userspace, or remove the {{User sandbox}} template.

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 specifically deal with taking in an arbitrary number of sorted lists greater than one, and then merging them all together into 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.

2-Way Merge

A 2-Way Merge has been studied extensively due to its key role in Merge sort.

Optimal 2-Way Merge

2-Way Merge has been studied extensively as a part o The merge function found in Merge sort, which only takes two sequences at a time, can also be used to merge together lists of size greater

 

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 at each time to merge. This technique is similar to the one used in Huffman coding.

Analysis

Ideal Merge

The Ideal Merge technique is another merge method that

In-Place Multiway Merging

References

• Knuth, Donald (1998). "Section 5.2.4: Sorting by Merging". Sorting and Searching. The Art of Computer Programming. Vol. 3 (2nd ed.). Addison-Wesley. pp. 158–168. ISBN 0-201-89685-0. {{cite book}}: Invalid |ref=harv (help)