Content deleted Content added
→K-way merging: propose merge Tags: nowiki added 2017 wikitext editor |
→K-way merging: clarify merge |
||
Line 44:
==K-way merging==
{{Merge from|K-way merge algorithm |discuss=Talk:K-way merge algorithm#Merge with merge algorithm page |date=December 2017 |section=yes}}</nowiki>
{{mvar|k}}-way merging generalizes binary merging to an arbitrary number {{mvar|k}} of sorted input lists. Applications of {{mvar|k}}-way merging arise in various sorting algorithms, including [[patience sorting]]<ref name="Chandramouli">{{Cite conference |last1=Chandramouli |first1=Badrish |last2=Goldstein |first2=Jonathan |title=Patience is a Virtue: Revisiting Merge and Sort on Modern Processors |conference=SIGMOD/PODS |year=2014}}</ref> and an [[external sorting]] algorithm that divides its input into {{math|''k'' {{=}} {{sfrac|1|''M''}} − 1}} blocks that fit in memory, sorts these one by one, then merges these blocks.{{r|toolbox}}{{rp|119–120}}
| |||