Merge algorithm: Difference between revisions

Revision as of 08:36, 18 April 2013

Revision as of 08:57, 8 December 2013

Line 23:

In [[parallel computing]], [[Array data structure|array]]s of sorted values may be merged efficiently using an [[all nearest smaller values]] computation.<ref>{{citation |first1=Omer |last1=Berkman |first2=Baruch |last2=Schieber |first3=Uzi |last3=Vishkin |author3-link=Uzi Vishkin |title=Optimal double logarithmic parallel algorithms based on finding all nearest smaller values |journal=Journal of Algorithms |volume=14 |pages=344–370 |year=1993 |issue=3 |doi=10.1006/jagm.1993.1018}}</ref>

Parallel merge can also be implemented using a divide-and-conquer algorithm, developed and shown in pseudo-code in.<ref>{{Harvnb|Cormen|Leiserson|Rivest|Stein|2009|p=800}}</ref> This algorithm performs well when combined with a fast sequential merge as a base case for merging of small arrays. Implementation using Intel's Threading Building Blocks (TBB) and Microsoft's Parallel Pattern Library (PPL) to run on [[multi-core processorsprocessor]]s is shown to perform well in practice.<ref>[http://drdobbs.com/high-performance-computing/229204454 V. J. Duvanenko, "Parallel Merge", Dr. Dobb's Journal, February 2011]</ref>

== See also ==