Content deleted Content added
No edit summary |
|||
Line 13:
The classic merge (the one used in [[merge sort]]) outputs the data item with the lowest key at each step; given some sorted lists, it produces a sorted list containing all the elements in any of the input lists, and it does so in time proportional to the sum of the lengths of the input lists.
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>▼
==Language support==
Line 21 ⟶ 19:
[[Python (programming language)]]'s standard library (since 2.6) also has a <code>merge()</code> function in the <code>heapq</code> module, that takes multiple sorted iterables, and merges them into a single iterator.[http://docs.python.org/library/heapq.html#heapq.merge]
==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=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 ==
{{reflist}}
* [[Donald Knuth]]. ''The Art of Computer Programming'', Volume 3: ''Sorting and Searching'', Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Pages 158–160 of section 5.2.4: Sorting by Merging. Section 5.3.2: Minimum-Comparison Merging, pp.197–207.
* [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]]. ''[[Introduction to Algorithms]]'', Third Edition. MIT Press and McGraw-Hill, 2009. ISBN 978-0-262-03384-8. Section 27.3: Multithreaded merge sort, pp. 797–804.
[[Category:Articles with example pseudocode]]
| |||