K-way merge algorithm: Difference between revisions

Revision as of 06:00, 21 November 2015

Revision as of 07:27, 21 November 2015

Line 7:

== 2-Way Merge ==

A 2-Way Merge, or a binary merge, has been studied extensively due to its key role in [[Merge sort]]. An example of such is the classic merge that appears frequently in merge sort examples. 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> ===

Line 14:

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

=== Hwang-Lin Merge ===

The classic merge is a simple sort that completes in linear time Ο(''n + m'').

== Optimal 2-Way Merge ==

Line 23 ⟶ 20:

The 2-Way Merge function found in merge sort can also be used as a tool to merge more than two lists.

=== Non-optimal ===

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 worst case running time for this algorithm reaches O(m² • n).

=== optimal merge pattern ===

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<ref>{{Cite book|title = DESIGN AND ANALYSIS OF ALGORITHMS|url = https://books.google.com/books?id=jYz1AAAAQBAJ|publisher = PHI Learning Pvt. Ltd.|date = 2013-08-21|isbn = 9788120348066|language = en|first = MANAS RANJAN|last = KABAT}}</ref>.

On the optimal merge pattern on the hand can reduce the running time to O(m • n • log m).

== Ideal Merge ==

Line 35 ⟶ 36:

# After the head element of the first list is removed, it is resorted according to the value of its new head element

# This repeats until all lists are empty

Depending on how ideal merge is implemented, the running time can vary. If ideal merge keeps its information in a sorted list, then inserting a new head element to the list would be done through a [[Linear search]] and the running time will be Θ(M•NM • N) where MN is the total number of elements in the sorted lists, and NM is the total number of sorted lists.

On the other hand, if the sorted items in a [[Heap (data structure)|heap]], then the running time becomes Θ(M log N).

On the other hand, if the sorted items in a [[Heap (data structure)|heap]], then the running time becomes Θ(MN log NM).

== In-Place Multiway Merging ==

== References ==