next up previous
Next: 8.1 The algorithm Up: Randomized Routing and Sorting Previous: 7 Construction of area

8 Sorting on butterflies


In this section we present a randomized algorithm for sorting tex2html_wrap_inline3809 packets on an tex2html_wrap_inline3811 -node butterfly network in tex2html_wrap_inline3813 steps using constant-size queues. The algorithm is based on the Flashsort algorithm of Reif and Valiant [32]. The main difference is that we use the algorithm for scheduling packets on leveled networks in place of their scheduling algorithm, which requires queues of size tex2html_wrap_inline3815 . A similar approach has been suggested previously by Pippenger [26].

Bruce Maggs
Mon Jul 22 22:57:44 EDT 1996