next up previous
Next: 1.4 Outline of the Up: 1 Introduction Previous: 1.2 Our approach to

1.3 The application of routing to sorting

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 tex2html_wrap_inline1951 steps and use tex2html_wrap_inline1953 -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].

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