Abstract
In this paper, we prove tight upper and lower bounds on the number or processors, information transfer, wire area and time needed to sort N numbers in a bounded-degree fixed-connection network. Our most important new results are: 1) the construction of an O(N))-node bounded-degree network capable of sorting N numbers in O(log N) word steps, 2) a proof that any network capable of sorting N(7 log N)-bit numbers in T bit-steps requires area A where AT2≥ &Ohgr;(N2log2N), and 3) the construction of a “small-constant-factor” bounded-degree network that sorts $N \Theta(N)$-bit numbers in T &equil; &thgr;(log N) bit steps with A &equil; &thgr;(N2) area.
Users
Please
log in to take part in the discussion (add own reviews or comments).