Merge algorithm: Difference between revisions

Revision as of 19:58, 12 September 2011

Revision as of 09:29, 14 December 2011

Line 3:

'''Merge algorithms''' are a family of [[algorithm]]s that run sequentially over multiple [[sorting algorithm|sorted]] lists, typically producing more sorted lists as output. This is well-suited for machines with [[tape drive]]s. Use has declined due to large [[random access memory|random access memories]], and many applications of merge algorithms have faster alternatives when a random-access memory is available.{{Fact|date=May 2009}}

The general merge algorithm has a set<!--non-technical use, don't link--> of [[Pointerpointer (computingcomputer programming)|pointer]]s p_0..n that point to positions in a set of lists L_0..n. Initially they point to the first item in each list. The algorithm is as follows:

While any of p_0..n still point to data inside of L_0..n instead of past the end:

Line 21:

==Parallel Merge==

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>{{citation|first1=Thomas|last1=Cormen|first2=Charles|last2=Leiserson|first3=Ronald|last3=Rivest|first4=Clifford |last3=Stein|title=Introduction to Algorithms|edition=Third Edition, MIT Press and McGraw-Hill, 2009|page=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>

== References ==