K-way merge algorithm: Difference between revisions

Revision as of 15:35, 22 December 2015

Revision as of 09:45, 23 December 2015

Line 53:

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