8 Sorting on butterflies

 

In this section we present a randomized algorithm for sorting packets on an -node butterfly network in 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 . A similar approach has been suggested previously by Pippenger [26].

• 8.1 The algorithm
• 8.2 Analysis
• 8.3 Bounding the load
• 8.4 Bounding the congestion at each switch
• 8.5 Bounding the cumulative delay
• 8.6 Putting it all together