GENERALIZED ROTATE SORT ON MESH-CONNECTED COMPUTERS WITH MULTIPLE BROADCASTING USING FEWER PROCESSORS

In this paper, we first present an O(log n) time sorting algorithm on 3-D mesh-connected computers with multiple broadcasting (abbreviated t o MCCMB) using n(1/2) X n(1/2) X n(1/2) processors. Our algorithm is d erived from rotate sort. Further, we also show that the result can be extended to n(1/k-1) x n(1/k-1) x ... x n(1/k-1) k-dimensional MCCMB o f size O(n(l+1/k-1)) to sort n data items in O(7(k-3) logn) time, for k greater than or equal to 3. The algorithm proposed is optimal speed- up while k is any constant. The contribution of this paper is to show that the proposed algorithm can be run in a higher dimensional MCCMB a nd using fewer processors but keeps the same time complexity as O(log n).