5,337
edits
Parallel Algorithms: Difference between revisions
→Integer Sorting
| Line 199: | Line 199: | ||
* Compute prefix sums of cardinality(0),.., cardinality(r-1) into global_ps(0),...,global_ps(r-1) | * Compute prefix sums of cardinality(0),.., cardinality(r-1) into global_ps(0),...,global_ps(r-1) | ||
* The rank of element <math>i</math> is <math>1+serial(i)+ps(v,s-1)+global_ps(v-1)</math> | * The rank of element <math>i</math> is <math>1+serial(i)+ps(v,s-1)+global_ps(v-1)</math> | ||
;Complexity | |||
* Step 1:<math>T=O(r),\;W=O(r)</math> per subarray. | |||
** Total: <math>T=O(r),\; W=O(n)</math> | |||
* Step 2: r computations each <math>T=O(\log(n/r)),\; W=O(n/r)</math> | |||
** Total <math>T=O(\log n),\; W=O(n)</math> | |||
* Step 3: <math>T=O(\log r),\; W=O(r)</math> | |||
* Step 4: <math>T=O(1)\; W=O(n)</math> | |||
* Total: <math>T=O(r + \log n),\; W=O(n)</math> | |||
;Notes | ;Notes | ||
* Running time is not poly-log | * Running time is not poly-log | ||
==Resources== | ==Resources== | ||