Parallel Sorting on Recursive Dual-Nets

In this paper, we propose an algorithm for parallel sorting on Recursive Dual-Net with an m-cube (Q_m) as its base network. The Recursive Dual-Net RDN^k(Q_m) for k >; 0 has 2(2^km+2^k-1) nodes and m + k links per node. The proposed sorting algorithm is based on the bitonic sorting. In an RDN^k(Q_m), assume that each node holds a single data item, the sorting algorithm runs in O((m2^k)²) computation steps and O((km2^k)²) communication steps.