Efficient sorting on the star graph interconnection network

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 previo usly known algorithm for the same problem. In addition to providing a new p aradigm 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 conte nts of all rows in each dimension of the (n - 1)-dimensional array. The sec ond algorithm presented in this paper is more efficient. It runs in O(n(2)) time and thus provides an asymptotic improvement over its predecessors. Ho wever, it is more elaborate as it uses an existing result for sorting optim ally on an (n - 1)-dimensional array.