Optimal VLSI Circuits for Sorting

Research output: Contribution to journalArticlepeer-review

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.

Original languageEnglish (US)
Pages (from-to)777-809
Number of pages33
JournalJournal of the ACM (JACM)
Volume35
Issue number4
DOIs
StatePublished - 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

Fingerprint Dive into the research topics of 'Optimal VLSI Circuits for Sorting'. Together they form a unique fingerprint.

Cite this