Content deleted Content added
m Added in wiki link to binary tree |
Added a section for External Sorting |
||
Line 1:
{{orphan|date=November 2015}}
In computer science, '''K-Way Merge Algorithms''' or '''Multiway Merges''' 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 generally find use in sorting algorithms such as [[Patience sorting|Patience Sorting]].
== 2-Way Merge ==
Line 52:
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.
== External Sorting<ref>{{Cite book|title = Data Structures and Algorithm Analysis in C++, Third Edition|url = https://books.google.com/books?id=AijEAgAAQBAJ|publisher = Courier Corporation|date = 2012-07-26|isbn = 9780486172620|language = en|first = Clifford A.|last = Shaffer}}</ref> ==
K-way merges find greater use in external sorting procedures. [[External sorting|External sorting algorithms]] are a class of sorting algorithms that can handle massive amounts of data. External sorting is required when the data being sorted do not fit into the main memory of a computing device (usually RAM) and instead they must reside in the slower external memory (usually a hard drive). K-way merge algorithms usually take place in the second stage of external sorting algorithms, much like they do for merge sort.
A Multiway merge like that discussed in ideal merge allows for the files outside of memory to be merged in fewer passes than in a binary merge. If there are 6 runs that need be merged together than a binary merge would need to take 3 merge passes, as opposed to a 6-way merges single merge pass. This reduction of merge passes is especially important considering the large amount of information that is usually being sorted in the first place, allowing for greater speed-ups while also reducing the amount of accesses to slower memory.
== References ==
| |||