Content deleted Content added
m Reverted edits by 122.252.244.186 (talk) to last version by Dolotta |
→External sorting: fix missing preposition Tags: Mobile edit Mobile web edit |
||
Line 91:
== External sorting ==
{{See also|External sorting}}
''k''-way merges are used in external sorting procedures.<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> [[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.
| |||