Content deleted Content added
→K-way merging: complexity of DC |
→K-way merging: applictaions |
||
Line 44:
The divide and conquer algorithm requires fewer than {{math|''n''⌈log ''k''⌉}} comparisons, i.e., less than half the number used by the heap-based algorithm.{{r|greene}}
===Applications===
Applications of {{mvar|k}}-way merging arise 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}}
A {{mvar|k}}-way in-memory merge sort can also be constructed from a {{mvar|k}}-way merge algorithm, but his provides no benefits over the ordinary binary merge sort.{{r|greene}}
== Parallel merge ==
| |||