Constant time sorting on reconfigurable meshes

We present a constant time sorting algorithm by adopting a 3D reconfigurable mesh with only O(n^3/2) processors. Our algorithm is developed on an n^1/2×n^1/2×n^1/2 3-D reconfigurable mesh. Moreover, we further extend the result to k-dimensional reconfigurable meshes for k⩾3. Consequently, an O(4 ^k+1) time sorting algorithm is obtained by adopting an n¹(k-1)/×n¹(k-1)/×...×n¹ (k-1)/k-D reconfigurable mesh of size O(n¹⁺¹(k-1)/). Hence, constant time sorting using O(n^1+ε) processors, where O<ε≪1, can be realized by adopting reconfigurable meshes of high dimensions