Merge algorithm: Difference between revisions

Revision as of 13:29, 29 November 2015

Revision as of 19:53, 29 November 2015

Line 46:

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 providesperforms noequally benefitsmany overcomparisons as the ordinary, binary merge sort.{{r|greene}}

== Parallel merge ==