Merge algorithm: Difference between revisions

Revision as of 20:15, 20 January 2018

Revision as of 19:59, 16 February 2018

Line 87:

== Parallel merge ==

A [[task parallelism|parallel]] version of the binary merge algorithm can serve as a building block of a [[Merge sort#Parallel merge sort|parallel merge sort]]. The following pseudocode demonstrates this algorithm in a [[fork-join model|parallel divide-and-conquer]] style (adapted from Cormen ''et al.''<ref name="clrs">{{Introduction to Algorithms|3}}</ref>{{rp|800}} with C++ implementation in <ref>{{Cite news|url=https://duvanenko.tech.blog/2018/01/14/parallel-merge/|title=Parallel Merge|date=2018-01-14|work=Algorithm Performance|access-date=2018-01-20|language=en-US}}</ref>). It operates on two sorted arrays {{mvar|A}} and {{mvar|B}} and writes the sorted output to array {{mvar|C}}. The notation {{mono|A[i...j]}} denotes the part of {{mvar|A}} from index {{mvar|i}} through {{mvar|j}}, exclusive.

'''algorithm''' merge(A[i...j], B[k...ℓ], C[p...q]) '''is'''