Quelltext der Seite Benutzer:ParAlgMergeSort/sandbox/Merge algorithm deutsch

<br />

== 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}}). 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'''
     '''inputs''' A, B, C : array
            i, j, k, ℓ, p, q : indices
 
     '''let''' m = j - i,
         n = ℓ - k
 
     '''if''' m < n '''then'''
         swap A and B  ''// ensure that A is the larger array: i, j still belong to A; k, ℓ to B''
         swap m and n
 
     '''if''' m ≤ 0 '''then'''
         '''return'''  ''// base case, nothing to merge''
 
     '''let''' r = ⌊(i + j)/2⌋
     '''let''' s = binary-search(A[r], B[k...ℓ])
     '''let''' t = p + (r - i) + (s - k)
     C[t] = A[r]
 
     '''in parallel do'''
         merge(A[i...r], B[k...s], C[p...t])
         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 with values smaller than the midpoint of the first, and a part with larger or equal values. (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. Dobb's Journal|date=2011|url=http://www.drdobbs.com/parallel/parallel-merge/229204454}}</ref>

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}}. To calculate the [[Analysis of parallel algorithms#Overview|span]] of the algorithm, it is necessary to derive a [[Recurrence relation]]. Since the two recursive calls of P-Merge are in parallel, only the costlier of the two calls needs to be considered. In the worst case, the maximum number of elements in one of the recursive calls is at most <math display="inline">\frac 3 4 n</math> since the array with more elements is perfectly split in half. Adding the <math>\Theta\left( \log(n)\right)</math> cost of the Binary Search, we obtain this recurrence as an upper bound:

<math>T_{\infty}^\text{merge}(n) = T_{\infty}^\text{merge}\left(\frac {3} {4} n\right) + \Theta\left( \log(n)\right)</math>

The solution is <math>T_{\infty}^\text{merge}(n) = \Theta\left(\log(n)^2\right)</math>, meaning that it takes that much time on an ideal machine with an unbounded number of processors.{{r|clrs}}{{rp|801–802}}

'''Note:''' The routine is not [[Sorting algorithm#Stability|stable]]: if equal items are separated by splitting {{mvar|A}} and {{mvar|B}}, they will become interleaved in {{mvar|C}}; also swapping {{mvar|A}} and {{mvar|B}} will destroy the order, if equal items are spread among both input arrays. As a result, when used for sorting, this algorithm produces a sort that is not stable.