| 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. This revised version was published online in June 2006 with corrections to the Cover Date. |
