5,337
edits
Parallel Algorithms: Difference between revisions
→Theorems
| Line 217: | Line 217: | ||
* The integer sorting algorithm can be applied to run in time <math>O(k(r^{1/k}+\log n))</math> and work <math>O(kn)</math> | * The integer sorting algorithm can be applied to run in time <math>O(k(r^{1/k}+\log n))</math> and work <math>O(kn)</math> | ||
Radix sort using the basic integer sort (BIS) algorithm. | Radix sort using the basic integer sort (BIS) algorithm.<br> | ||
If your range is 0 to n and and your radix is <math>\sqrt{n}</math> then you will need <math>log_{\sqrt{n}}(r) = 2</math> rounds. | |||
==Resources== | ==Resources== | ||