K-way merge algorithm: Difference between revisions

Revision as of 22:29, 19 November 2015

Revision as of 22:55, 19 November 2015

Line 4:

[[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 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.

__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]]. The classic merge outputs the data item with the lowest key at each step; given some sorted lists, it produces a sorted list containing all the elements in any of the input lists, and it does so in time proportional to the sum of the lengths of the input lists.

=== Example<ref>{{Cite web|title = ALGORITHM TO MERGE SORTED ARRAYS (Java, C++) {{!}} Algorithms and Data Structures|url = http://www.algolist.net/Algorithms/Merge/Sorted_arrays|website = www.algolist.net|accessdate = 2015-11-19}}</ref> ===

Assume, that we have two arrays A[0..m-1] and B[0..n-1] that are sorted in ascending order and we want to merge them into an array C[0..m+n-1] with the same order. 

# Introduce read-indices '''i''', '''j''' to traverse arrays A and B, accordingly. Introduce write-index '''k''' to store position of the first free cell in the resulting array. By default '''i''' = '''j''' = '''k''' = 0.

# At each step: if both indices are in range ('''i''' < m and '''j''' < n), choose minimum of (A['''i'''], B['''j''']) and write it to C['''k''']. Otherwise go to step 4.

# Increase '''k''' and index of the array, algorithm located minimal value at, by one. Repeat step 2.

# Copy the rest values from the array, which index is still in range, to the resulting array.

== 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

[[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 2-Way Merge function found in merge sort can also be used as a tool to merge more than two lists.

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]].

Let D={n₁, ... , n_k} be the set of sequences to be merged. Pick n_i, n_j∈ D and then merge them together using the merge function. The new set D is then D' = (D - {n_i, n_j}) ∪ {n_i+n_j}. This process is repeated until |D| = 1. The question then becomes how to pick n_i and n_j. How the merge algorithm picks n_i and n_j determines the cost of the overall algorithm.

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]]. The algorithm picks  n_i, n_j∈ D such that |n| ≥ |n_i| and |n| ≥ |n_j| ∀ n∈ D.

=== Analysis ===

== Ideal Merge ==

Line 39 ⟶ 45:

| ref = harv}}

* {{cite book|author1=Thomas H Cormen|author2=Charles E Leiserson|author3=Ronald L Rivest|coauthors=Clifford Stein|title=Introduction To Algorithms|url=http://books.google.com/books?id=NLngYyWFl_YC&pg=PA11|year=2001|publisher=MIT Press|isbn=978-0-262-03293-3|pages=28–29}}