Content deleted Content added
→Application: Fixed typo Tags: Mobile edit Mobile web edit Advanced mobile edit |
m Fixed bugs in the pseudocode for Paraler merge. originally it would fail when, for example if merge were given two arrays both having the size of 1 the psudo code would immediately exit without saving the result or sorting it. There was also an infinite loop that results in stackoverflow whenever A[r] is the largest value in both arrays. Tags: Reverted Visual edit |
||
Line 97:
'''if''' m < n '''then'''
'''if''' m
'''return''' ''// base case, nothing to merge''
'''let''' r = ⌊(i + j)/2⌋
'''let''' s = binary-search(A[r], B[k...ℓ]) ''// index where B[k...s] ≤ A[r] ≤ B[s...l] for all values''
'''let''' t = p + (r - i) + (s - k)
C[t] = A[r]
'''in parallel do'''
merge(A[i...r-1], B[k...s-1], C[p...t-1]) ''// all values are smaller or equal to A[r]''
merge(A[r+1...j], B[s...ℓ], C[t+1...q]) ''// all values are greater or equal to A[r]''
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">{{citation| author=Victor J. Duvanenko| title=Parallel Merge| journal=Dr. Dobb's Journal| date=2011| url=http://www.drdobbs.com/parallel/parallel-merge/229204454}}</ref>
| |||