K-way merge algorithm: Difference between revisions

Revision as of 19:20, 19 November 2015

Revision as of 22:18, 19 November 2015

Line 2:

<!-- EDIT BELOW THIS LINE -->

[[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 arespecifically thedeal classwith oftaking mergein algorithmsan thatarbitrary takenumber asof inputsorted alists group of moregreater than one sorted lists, and outputthen merging them all together into a single sorted list.

__TOC__

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 ofo [[Merge sort]]. It would be trivial to simply walk through ''S'' and merge together two sorted lists at a time using theThe merge function found in Merge sort, untilwhich only onetakes finaltwo listsequences isat left.a Thetime, questioncan thenalso becomesbe howused to findmerge thetogether optimallists mergeof size greater pattern.

[[File:HuffmanCodeAlg.png|thumb|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 ==

**

<references />

**

**