An Optimal Multiway Mergesort Algorithm for a Simplified 2D ARPBS

M. He and S.Q. Zheng (USA)


Parallel Algorithms and Architectures, Interconnection Networks, Optical Interconnects, Sorting


We present a multiway mergesort algorithm for a simplified n n 2D ARPBS (Array with Reconfigurable Pipelined Bus System) to sort n2 elements in O(log n) time. This al gorithm is optimal, considering the number of comparisons required is O(n2 log n) which is the same as the sequential complexity of the problem.

Important Links:

Go Back