Sorting n numbers on n*n reconfigurable meshes with buses
M. Nigam, Sartaj K. Sahni · 2002
The authors show how column sort and rotate sort can be implemented on the different reconfigurable mesh with buses (RMB) architectures that have been proposed in the literature. On all of these proposed RMB architectures, the authors are able to sort n numbers on an n*n configuration in O(1) time. For the PARBUS RMB architecture the authors' column sort and rotate sort implementations are simpler than the O(1) sorting algorithms. Furthermore, their sorting algorithms use fewer bus broadcasts. For the RMESH RMB architecture, their algorithms are the first to sort n numbers on an n*n configuration in O(1) time. They also observe that rotate sort can be implemented on N*N*. . .*N k+1 dimensional RMB architectures so as to sort N/sup k/ elements in O(1) time.>