Generalized Algorithm for Parallel Sorting on Product Networks

If G isaconnected graph with N nodes, its r dimensional product contains N r nodes. We present an algorithm which sorts N r keys stored in the rdimensional product of any graph G in O(r²S(N)) time where S(N) depends on G. We show that for any graph G, S(N) is bounded above by O(N), establishing an upper bound of O(r²N) for the time complexity of sorting N r keys on any product network. When r is xed, this leads to the asymptotic complexity O(N) to sort N r keys, which is optimal for several instances of product networks. There aregraphs for which S(N) =O(Log² N) which leads to the asymptotic running time of O(Log² N)