5,337
edits
Parallel Algorithms: Difference between revisions
→Technique: Partitioning
| Line 102: | Line 102: | ||
* Merging: Given two sorted arrays, A and B, create a sorted array C consisting of elements in A and B | * Merging: Given two sorted arrays, A and B, create a sorted array C consisting of elements in A and B | ||
* Ranking: Given an element x, find <math>Rank(x, A) = i</math> defined such that <math>A(i) \leq x \leq A(i+1)</math> | * Ranking: Given an element x, find <math>Rank(x, A) = i</math> defined such that <math>A(i) \leq x \leq A(i+1)</math> | ||
** Note the book sometimes uses <math>Rank(i,B)</math> to denote <math>Rank( | ** Note the book sometimes uses <math>Rank(i,B)</math> to denote <math>Rank(A(i), B)</math>. | ||
;Equivalence of Merging and Ranking | ;Equivalence of Merging and Ranking | ||