K-way merge algorithm: Difference between revisions

Revision as of 12:19, 23 April 2016

Revision as of 04:00, 8 June 2016

Line 56:

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