Bitonic Sort on a Mesh-Connected Parallel Computer

David Nassimi, Sartaj Sahni

Research output: Contribution to journalArticlepeer-review

163 Scopus citations

Abstract

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

Original languageEnglish (US)
Pages (from-to)2-7
Number of pages6
JournalIEEE Transactions on Computers
VolumeC-28
Issue number1
DOIs
StatePublished - Jan 1979
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics

Keywords

  • Bitonic sort
  • SIMD machine
  • complexity
  • mesh-connected parallel computer
  • parallel sorting

Fingerprint

Dive into the research topics of 'Bitonic Sort on a Mesh-Connected Parallel Computer'. Together they form a unique fingerprint.

Cite this