K-Way Bitonic Sort

Toshio Nakatani; Shing Tsaan Huang; Bruce W. Arden; Satish K. Tripathi

doi:10.1109/12.16506

K-Way Bitonic Sort

Toshio Nakatani
, Shing Tsaan Huang
, Bruce W. Arden
, Satish K. Tripathi

Princeton University
National Tsing Hua University
University of Rochester

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

31 Scopus citations

Abstract

This paper presents k-way bitonic sort, which is a generalization of Batcher's bitonic sort. This algorithm is based on a 4-way decomposition instead of a two-way decomposition. We prove that Batcher's bitonic sequence decomposition theorem still holds with this multiway decomposition. This leads to applications of sorting networks with bitonic sorters of arbitrary or mixed sizes.

Original language	English
Pages (from-to)	283-288
Number of pages	6
Journal	IEEE Transactions on Computers
Volume	38
Issue number	2
DOIs	https://doi.org/10.1109/12.16506
State	Published - Feb 1989

Keywords

Bitonic sort
parallel processing
parallel sorting

Access to Document

10.1109/12.16506

Cite this

@article{ab3ede632b224072b294049177902f54,

title = "K-Way Bitonic Sort",

abstract = "This paper presents k-way bitonic sort, which is a generalization of Batcher's bitonic sort. This algorithm is based on a 4-way decomposition instead of a two-way decomposition. We prove that Batcher's bitonic sequence decomposition theorem still holds with this multiway decomposition. This leads to applications of sorting networks with bitonic sorters of arbitrary or mixed sizes.",

keywords = "Bitonic sort, parallel processing, parallel sorting",

author = "Toshio Nakatani and Huang, \{Shing Tsaan\} and Arden, \{Bruce W.\} and Tripathi, \{Satish K.\}",

year = "1989",

month = feb,

doi = "10.1109/12.16506",

language = "English",

volume = "38",

pages = "283--288",

journal = "IEEE Transactions on Computers",

issn = "0018-9340",

publisher = "IEEE Computer Society",

number = "2",

}

TY - JOUR

T1 - K-Way Bitonic Sort

AU - Nakatani, Toshio

AU - Huang, Shing Tsaan

AU - Arden, Bruce W.

AU - Tripathi, Satish K.

PY - 1989/2

Y1 - 1989/2

N2 - This paper presents k-way bitonic sort, which is a generalization of Batcher's bitonic sort. This algorithm is based on a 4-way decomposition instead of a two-way decomposition. We prove that Batcher's bitonic sequence decomposition theorem still holds with this multiway decomposition. This leads to applications of sorting networks with bitonic sorters of arbitrary or mixed sizes.

AB - This paper presents k-way bitonic sort, which is a generalization of Batcher's bitonic sort. This algorithm is based on a 4-way decomposition instead of a two-way decomposition. We prove that Batcher's bitonic sequence decomposition theorem still holds with this multiway decomposition. This leads to applications of sorting networks with bitonic sorters of arbitrary or mixed sizes.

KW - Bitonic sort

KW - parallel processing

KW - parallel sorting

UR - https://www.scopus.com/pages/publications/0024610835

U2 - 10.1109/12.16506

DO - 10.1109/12.16506

M3 - Article

AN - SCOPUS:0024610835

SN - 0018-9340

VL - 38

SP - 283

EP - 288

JO - IEEE Transactions on Computers

JF - IEEE Transactions on Computers

IS - 2

ER -

K-Way Bitonic Sort

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this