ISSN:
1572-9451
Source:
Springer Online Journal Archives 1860-2000
Topics:
Electrical Engineering, Measurement and Control Technology
Notes:
Abstract Two algorithms for sorting n! numbers on an n-star interconnection network are described. Both algorithms are based on arranging the n! processors of the n-star in a virtual (n - 1)- dimensional array. The first algorithm runs in O(n 3 log n time. This performance matches that of the fastest previously known algorithm for the same problem. In addition to providing a new paradigm for sorting on the n-star, the proposed algorithm has the advantage of being considerably simpler to state while requiring no recursion in its formulation. Its idea is to sort the input by repeatedly sorting the contents of all rows in each dimension of the (n - 1〉algorithm presented in this paper is more efficient. It runs in O(n 2) time and thus provides an asymptotic improvement over its predecessors. However, it is more elaborate as it uses an existing result for sorting optimally on an (n-1)-dimensional array.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1023/A:1019146428683
