Merge algorithm: Difference between revisions

Revision as of 04:51, 13 November 2012

Revision as of 04:52, 13 November 2012

Line 24:

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 processors 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 ==

* [[Join (relational algebra)]]

* [[Join (SQL)]]

* [[Join (Unix)]]

==Notes==

Line 31 ⟶ 36:

* [[Donald Knuth]]. ''The Art of Computer Programming'', Volume 3: ''Sorting and Searching'', Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Pages 158&ndash;160 of section 5.2.4: Sorting by Merging. Section 5.3.2: Minimum-Comparison Merging, pp.&nbsp;197&ndash;207.

*{{Citation |first1=Thomas |last1=Cormen |authorlink1=Thomas H. Cormen |first2=Charles |last2=Leiserson |authorlink2=Charles E. Leiserson |first3=Ronald |last3=Rivest |authorlink3=Ronald L. Rivest |first4=Clifford |last4=Stein |authorlink4=Clifford Stein |title=[[Introduction to Algorithms]] |edition=Third Edition |publisher=MIT Press and McGraw-Hill |year=2009 |isbn=978-0-262-03384-8 |chapter=Section 27.3: Multithreaded merge sort |pages=797&ndash;804 }}

== See also ==

* [[Join (relational algebra)]]

* [[Join (SQL)]]

* [[Join (Unix)]]

{{DEFAULTSORT:Merge Algorithm}}