5,343
edits
Parallel Algorithms: Difference between revisions
→Technique: Partitioning
| Line 100: | Line 100: | ||
==Technique: Merge Sorting Cluster== | ==Technique: Merge Sorting Cluster== | ||
===Technique: Partitioning=== | ===Technique: Partitioning=== | ||
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 Rank(x, A) = i 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(a_i, B)</math>. | |||
;Equivalence of Merging and Ranking | ;Equivalence of Merging and Ranking | ||