The recently discovered Shear-sort algorithm requires log2n iterations of row and column sorts for ordering n2 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 log2n 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. © 1989.