Content deleted Content added
Fixed link to C# (previously pointed to the letter C) and added link to C++ |
Pointed out that the Divide-And-Conquer Merge is not stable, and leads to a sort that will not be stable. |
||
Line 113:
merge(A[r+1...j], B[s...ℓ], C[t+1...q])
The algorithm operates by splitting either {{mvar|A}} or {{mvar|B}}, whichever is larger, into (nearly) equal halves. It then splits the other array into a part that is smaller than the midpoint of the first, and a part that is larger. (The [[binary search]] subroutine returns the index in {{mvar|B}} where {{math|''A''[''r'']}} would be, if it were in {{mvar|B}}; that this always a number between {{mvar|k}} and {{mvar|ℓ}}.) Finally, each pair of halves is merged [[Divide and conquer algorithm|recursively]], and since the recursive calls are independent of each other, they can be done in parallel. Hybrid approach, where serial algorithm is used for recursion base case has been shown to perform well in practice <ref name="vjd">{{cite| author=Victor J. Duvanenko| title=Parallel Merge| journal=Dr. Dobbs Journal| date=2011| url=http://www.drdobbs.com/parallel/parallel-merge/229204454}}</ref> When used for sorting, this algorithm produces a sort that is not stable.
The [[Analysis of parallel algorithms#Overview|work]] performed by the algorithm for two arrays holding a total of {{mvar|n}} elements, i.e., the running time of a serial version of it, is {{math|''O''(''n'')}}. This is optimal since {{mvar|n}} elements need to be copied into {{mvar|C}}. Its critical path length, however, is {{math|Θ(log<sup>2</sup> ''n'')}}, meaning that it takes that much time on an ideal machine with an unbounded number of processors.{{r|clrs}}{{rp|801–802}}
| |||