Merge algorithm: Difference between revisions

Revision as of 19:47, 5 August 2015

Revision as of 14:19, 13 August 2015

Line 12:

# find out which of those pointers points to the item with the lowest key; advance one of those pointers to the next item in its list

== Analysis ==

Merge algorithms generally run in time proportional to the sum of the lengths of the lists; merge algorithms that operate on large numbers of lists at once will multiply the sum of the lengths of the lists by the time to figure out which of the pointers points to the lowest item, which can be accomplished with a [[heap (data structure)|heap]]-based [[priority queue]] in [[Big O notation|O]](log ''n'') time, for O(''m'' log ''n'') time, where ''n'' is the number of lists being merged and ''m'' is the sum of the lengths of the lists. When merging two lists of length ''m'', there is a lower bound of 2''m'' −− 1 comparisons required in the worst case.

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.

== Language support ==

Some [[computer language]]s provide built-in merge support for [[collections]].

Line 30:

In [[CSharp|C#]], merge can be achieved with [[Language Integrated Query|LINQ]].

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

Line 41:

* [[Join (Unix)]]

== Notes ==

{{reflist}}

== References ==

* [[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;160158–160 of section 5.2.4: Sorting by Merging. Section 5.3.2: Minimum-Comparison Merging, pp.&nbsp;197&ndash;207197–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 |publisher=MIT Press and McGraw-Hill |year=2009 |isbn=978-0-262-03384-8 |chapter=Section 27.3: Multithreaded merge sort |pages=797&ndash;804797–804 }}

{{DEFAULTSORT:Merge Algorithm}}