Content deleted Content added
Added in Ideal Merge implementation |
→Binary Tree Implementation: Finished the graphics for the binary tree implementation, and also merged the two 2-way merge sections |
||
Line 7:
<!-- EDIT BELOW THIS LINE -->
In [[computer science]]''', K-Way Merge Algorithms''' are a specific type of [[Merge algorithm|Sequence Merge Algorithms]] that specialize in taking in multiple sorted lists and merging them into a single sorted list. These merge algorithms generally refer to merge algorithms that take in a number of sorted lists greater than two. 2-Way Merges are referred to as binary merges on the other hand and are also utilized in k-way merge algorithms. K-way merge algorithms often find use in
__TOC__
Line 21:
# Copy the rest values from the array, which index is still in range, to the resulting array.
===
If the number of sorted lists k is greater than 2, the 2-Way Merge function found in merge sort can still be used to merge everything into a single sorted list.[[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.]]
==== Non-optimal ====
Let D={n<sub>1</sub>, ... , n<sub>k</sub>} be the set of sequences to be merged. Pick n<sub>i</sub>, n<sub>j</sub>∈ D and then merge them together using the merge function. The new set D is then D' = (D - {n<sub>i</sub>, n<sub>j</sub>}) ∪ {n<sub>i</sub>+n<sub>j</sub>}. This process is repeated until |D| = 1. The question then becomes how to pick n<sub>i</sub> and n<sub>j</sub>. How the merge algorithm picks n<sub>i</sub> and n<sub>j</sub> determines the cost of the overall algorithm. The worst case running time for this algorithm reaches O(m<sup>2</sup> • 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<sub>i</sub>, n<sub>j</sub>∈ D such that |n| ≥ |n<sub>i</sub>| and |n| ≥ |n<sub>j</sub>| ∀ 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>.
Line 34 ⟶ 33:
== Ideal Merge ==
The Ideal Merge technique is another merge method for merging greater than two lists except it does not use the 2-Way merge technique. The ideal merging technique was discussed and saw use as a part of UnShuffle Sort.<ref>'''Art S. Kagel''', ''Unshuffle Algorithm, Not Quite a Sort?'', Computer Language Magazine, 3(11), November 1985.</ref>
Given a group of sorted lists ''S'' that we want to merge into list ''S''', the algorithm is as follows:
Line 52 ⟶ 51:
Very fast merge sort - Google Project Hosting|url = https://code.google.com/p/kway/|website = code.google.com|accessdate = 2015-11-22}}</ref><blockquote><code>{5, 10, 15, 20}</code></blockquote><blockquote><code>{10, 13, 16, 19}</code></blockquote><blockquote><code>{2, 19, 26, 40}</code> </blockquote><blockquote><code>{18, 22, 23, 24}</code></blockquote>We start with the heads of each array and then build a binary tree from there.
[[File:Binary Ideal Merge 1.png|centre|thumb]]
The nodes from each array are compared to each other, before the value 2 is found as the lowest list head element. That value is then popped off, and its leaf is refilled with the next value in the list.
[[File:Binary Ideal Merge 2.png|centre|thumb]]
The value 2 is repopulated by the next value in the sorted list, 19. The comparisons end with 5 being the smallest value, and thus the next value to be popped off. This continues until all of the sorted lists are empty.
== References ==
| |||