Sorting on the OTIS-mesh

In this paper we present sorting algorithms on the recently introduced N² processor OTIS-mesh, a network with diameter 4√N-3 consisting of N connected meshes of size √N×√N. We show that k-k sorting can be done in 8√N+O(N^1/3) steps for k=1, 2, 3, 4 and in 2k√N+O(kN^1/3) steps for k>4 with constant buffer-size for all k. We show how our algorithms can be modified to achieve 4√N+O(N^1/3) steps for k=1, 2, 3, 4 and k√N+O(kN^1/3) steps for k>4 in the average case. Finally, we show a lower bound of max{4√N, 1/√2 k√N} steps for k-k sorting