K-way merge algorithm: Difference between revisions

Revision as of 16:49, 4 February 2017

Revision as of 13:49, 14 February 2017

Line 101:

== 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|first = Clifford A.|last = Shaffer}}</ref> ==

K-way merges find greategreat 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 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 then 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.