Sorting, selection, and routing on the array with reconfigurable optical buses
Sanguthevar Rajasekaran, Sartaj K. Sahni · IEEE Transactions on Parallel and Distributed Systems · 1997
In this paper, we present efficient algorithms for sorting, selection, and packet routing on the AROB (Array with Reconfigurable Optical Buses) model. One of our sorting algorithms sorts n general keys in O(1) time on an AROB of size n/sup /spl epsiv///spl times/n for any constant /spl epsiv/>0. We also show that selection from out of n elements can be done in randomized O(1) time employing n processors. Our routing algorithm can route any h-relation in randomized O(h) time. All these algorithms are clearly optimal.