Packet routing and sorting have long been known to be closely linked problems on fixed-connection networks. In his fundamental paper, Batcher [4] showed that an algorithm for sorting on a network can usually be converted into an algorithm for packet routing. Reif and Valiant [32], on the other hand, described a method for converting a routing algorithm into a randomized sorting algorithm. As a consequence, they derived randomized sorting algorithms for hypercubes and butterflies that run in steps and use -size queues.

In this paper we combine the Reif-Valiant approach with our routing strategy to devise improved algorithms for sorting on fixed-connection networks. For each network considered, the algorithm runs in time proportional to the diameter of the network, and uses constant-size queues. Such algorithms were previously known only for bounded-dimensional arrays [16, 35].

Mon Jul 22 22:57:44 EDT 1996