Optimal VLSI Circuits for Sorting

Richard Cole; Alan Siegel

doi:10.1145/48014.48017

Optimal VLSI Circuits for Sorting

Richard Cole, Alan Siegel

Computer Science

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

Abstract

This work describes a large number of constructions for sorting N integers in the range [0, M - 1], for N ≤ M ≤ N₂, for the standard VLSI bit model. Among other results, we attain: VLSI sorter constructions that are within a constant factor of optimal size, for all M and almost all running times T. a fundamentally new merging network for sorting numbers in a bit model. new organizational approaches for optimal tuning of merging networks and the proper management of data flow.

Original language	English (US)
Pages (from-to)	777-809
Number of pages	33
Journal	Journal of the ACM (JACM)
Volume	35
Issue number	4
DOIs	https://doi.org/10.1145/48014.48017
State	Published - Oct 1 1988

Keywords

Area/time tradeoffs
integer sorting

ASJC Scopus subject areas

Software
Control and Systems Engineering
Information Systems
Hardware and Architecture
Artificial Intelligence

Access to Document

10.1145/48014.48017

Cite this

@article{e2cadcb2d1da495e9b91fff71dd001a6,

title = "Optimal VLSI Circuits for Sorting",

abstract = "This work describes a large number of constructions for sorting N integers in the range [0, M - 1], for N ≤ M ≤ N2, for the standard VLSI bit model. Among other results, we attain: VLSI sorter constructions that are within a constant factor of optimal size, for all M and almost all running times T. a fundamentally new merging network for sorting numbers in a bit model. new organizational approaches for optimal tuning of merging networks and the proper management of data flow.",

keywords = "Area/time tradeoffs, integer sorting",

author = "Richard Cole and Alan Siegel",

year = "1988",

month = oct,

day = "1",

doi = "10.1145/48014.48017",

language = "English (US)",

volume = "35",

pages = "777--809",

journal = "Journal of the ACM (JACM)",

issn = "0004-5411",

publisher = "Association for Computing Machinery (ACM)",

number = "4",

}

TY - JOUR

T1 - Optimal VLSI Circuits for Sorting

AU - Cole, Richard

AU - Siegel, Alan

PY - 1988/10/1

Y1 - 1988/10/1

N2 - This work describes a large number of constructions for sorting N integers in the range [0, M - 1], for N ≤ M ≤ N2, for the standard VLSI bit model. Among other results, we attain: VLSI sorter constructions that are within a constant factor of optimal size, for all M and almost all running times T. a fundamentally new merging network for sorting numbers in a bit model. new organizational approaches for optimal tuning of merging networks and the proper management of data flow.

AB - This work describes a large number of constructions for sorting N integers in the range [0, M - 1], for N ≤ M ≤ N2, for the standard VLSI bit model. Among other results, we attain: VLSI sorter constructions that are within a constant factor of optimal size, for all M and almost all running times T. a fundamentally new merging network for sorting numbers in a bit model. new organizational approaches for optimal tuning of merging networks and the proper management of data flow.

KW - Area/time tradeoffs

KW - integer sorting

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

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

U2 - 10.1145/48014.48017

DO - 10.1145/48014.48017

M3 - Article

AN - SCOPUS:0024091389

SN - 0004-5411

VL - 35

SP - 777

EP - 809

JO - Journal of the ACM (JACM)

JF - Journal of the ACM (JACM)

IS - 4

ER -

Optimal VLSI Circuits for Sorting

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this