A fast parallel sorting algorithm on the k-dimensional reconfigurable mesh

We presents a new parallel sorting algorithm on the k-dimensional reconfigurable mesh which is a generalized version of the well-studied (two dimensional) reconfigurable mesh. We introduce a new mapping technique which combines the enlarged bandwidth of the multidimensional mesh and the feature of the reconfigurable mesh. Using our mapping technique, we show that N^k numbers can be sorted in O(4^k ) (constant time for small k) time on a k+1 dimensional reconfigurable mesh of size k+1 times N×N×…×N. In addition, it is shown that the number of 1´s in a 0/1 array of k times size N×N×…×N can be computed in O(log* N+log k) time on reconfigurable k times mesh of size N×N×…×N