Bitonic Sort on a Mesh-Connected Parallel Computer

Abstract

An O(n) algorithm to sort n²elements on an Illiac IV-like n × n mesh-connected processor array is presented. This algorithm sorts the n²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²elements into snake-like row-major order. Extensions to the case of a j-dimensional processor array are discussed.