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 to MCCMB) using n1/2×n1/2×n1/2 processors. Our algorithm is derived from rotate sort. Further, we also show that the result can be extended to k-dimensional MCCMB of size to sort n data items in O(7k−3 log n) time, for k≥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 and using fewer processors but keeps the same time complexity as O(log n).