K-way merge algorithm: Difference between revisions

Revision as of 08:04, 21 November 2015

Revision as of 05:35, 22 November 2015

Line 7:

<!-- EDIT BELOW THIS LINE -->

[[Merge algorithm|Sequence'''K-Way Merge Algorithms]]''' are a familyspecific type of [[algorithmsMerge algorithm|Sequence Merge Algorithms]] that runspecialize sequentiallyin overtaking in multiple sorted lists, typicallyand producingmerging morethem sortedinto listsa assingle outputsorted list. K-WayThese Mergemerge Algorithmsalgorithms specificallygenerally dealrefer withto takingmerge inalgorithms anthat arbitrarytake in a number of sorted lists greater than one,two. and2-Way thenMerges mergingare themreferred allto togetheras intobinary amerges singleon sortedthe listother hand and are also utilized in k-way merge algorithms.

__TOC__

Line 34:

== Ideal Merge ==

The Ideal Merge technique is another merge method for merging greater than two lists. The ideal merging technique was first discussed 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 41:

# 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

The head elements are generally stored in a priority queue. Depending on how idealthe priority mergequeue 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 • N) where N is the total number of elements in the sorted lists, and M 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 Θ(N log M).

=== Binary Tree Implementation ===

As an example, the above technique can be implemented using a binary tree for its priority queue<ref>{{Cite book|title = Fundamentals of data structures|url = https://books.google.com/books?id=kdRQAAAAMAAJ|publisher = Computer Science Press|date = 1983-01-01|isbn = 9780914894209|language = en|first = Ellis|last = Horowitz|first2 = Sartaj|last2 = Sahni}}</ref>. This can help limit the number of comparisons between the element heads. The binary tree is built containing the results of comparing the head of each array. The topmost node of the binary tree is then popped off and its leaf is refilled with the next element in its array.

As an example, let's say we have 4 sorted arrays:<ref>{{Cite web|title = kway -

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.

            2

              /       \

            2           5

          /   \       /   \

        18     2    10     5

== References ==