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].