Two nearly optimal sorting algorithms for mesh-connected processor arrays using shear-sort

Abstract

The recently discovered Shear-sort algorithm requires log2_n iterations of row and column sorts for ordering n² elements on an n×n mesh-connected array of processors. Although the method is extremely simple and practical, it falls short by a factor of log₂n of the well-known lower bound for sorting on a mesh-connected computer. Recursive application of Shear-sort in a square array leads to the first proposed O(n) algorithm. A slightly more complicated iterative algorithm, also executing in O(n) steps is presented next. Both algorithms are surprisingly simple and are the result of the adoption of an entirely new approach to two-dimensional sorting.