An efficient sorting algorithm on the multi-mesh network

The shear-sort algorithm [19] on an SIMD mesh model requires 4 root N + o(root N) time for sorting N elements arranged on a root N x root N mesh. In this paper, we present an algorithm for sorting N elements in time O(N-1/4) On an SIMD Multi-Mesh architecture, thereby significantly improving the order of the time complexity. The Multi-Mesh architecture [23], [24] is built around n(2) blocks, where each block is an n x n mesh with n = N-1/4, SO that each processor will uniformly have four neighbors in the final topology.