Sorting in constant number of row and column phases on a mesh

An algorithm for sorting on a mesh by alternately transforming the rows and columns is presented. The algorithm runs in a constant number of row- and column-transformation phases (sixteen phases), an improvement over the previous best upper bound ofO(log logm) phases,m being the number of rows in the mesh. A corresponding lower bound of five phases is also shown.This research was supported by the National Science Foundation under Grant DCR-84-51396, and by IBM Corporation under Grant D8400622.