Bitonic Sort on a Mesh-Connected Parallel Computer

David Nassimi; Sartaj Sahni

doi:10.1109/TC.1979.1675216

Bitonic Sort on a Mesh-Connected Parallel Computer

David Nassimi, Sartaj Sahni

Research output: Contribution to journal › Article › peer-review

178 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 language	English (US)
Pages (from-to)	2-7
Number of pages	6
Journal	IEEE Transactions on Computers
Volume	C-28
Issue number	1
DOIs	https://doi.org/10.1109/TC.1979.1675216
State	Published - Jan 1979
Externally published	Yes

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

Access to Document

10.1109/TC.1979.1675216

Cite this

@article{d3aaac89e5cd4bdcb2a577fd352854a2,

title = "Bitonic Sort on a Mesh-Connected Parallel Computer",

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.",

keywords = "Bitonic sort, SIMD machine, complexity, mesh-connected parallel computer, parallel sorting",

author = "David Nassimi and Sartaj Sahni",

year = "1979",

month = jan,

doi = "10.1109/TC.1979.1675216",

language = "English (US)",

volume = "C-28",

pages = "2--7",

journal = "IEEE Transactions on Computers",

issn = "0018-9340",

publisher = "IEEE Computer Society",

number = "1",

}

TY - JOUR

T1 - Bitonic Sort on a Mesh-Connected Parallel Computer

AU - Nassimi, David

AU - Sahni, Sartaj

PY - 1979/1

Y1 - 1979/1

N2 - 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.

AB - 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.

KW - Bitonic sort

KW - SIMD machine

KW - complexity

KW - mesh-connected parallel computer

KW - parallel sorting

UR - http://www.scopus.com/inward/record.url?scp=0018291773&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0018291773&partnerID=8YFLogxK

U2 - 10.1109/TC.1979.1675216

DO - 10.1109/TC.1979.1675216

M3 - Article

AN - SCOPUS:0018291773

SN - 0018-9340

VL - C-28

SP - 2

EP - 7

JO - IEEE Transactions on Computers

JF - IEEE Transactions on Computers

IS - 1

ER -

Bitonic Sort on a Mesh-Connected Parallel Computer

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this