Bitonic Sort on a Mesh-Connected Parallel Computer

An O(n) algorithm to sort n 2 elements on an Illiac IV-like n × n mesh-connected processor array is presented. This algorithm sorts the n 2 elements into row-major order and is an adaptation of Batcher's bitonic sort. A slight modification of our algorithm yields an O(n) algorithm to sort n 2 elements into snake-like row-major order. Extensions to the case of a j-dimensional processor array are discussed.