Minimum storage sorting networks

Research output: Contribution to journalArticlepeer-review

Abstract

This paper analyzes how to sort n k-bit numbers in a minimum storage network. The techniques also give new AT2 lower bounds for a VLSI sorting model. The principal results in this paper are as follows. * Lower bounds are given for the minimum storage (and area) needed to sort n k-bit numbers, and accompanying upper bounds (sorting networks) are presented, which match the lower bounds, up to a constant factor. * Sharp bounds are derived, which demonstrate that theminimum storage requirements depend quite strongly on the I/O schedule, and on the sorting model. * AT2 lower bounds are established for a VLSI device that sorts n k-bit numbers where k ≫ log n.

Original languageEnglish (US)
Pages (from-to)355-361
Number of pages7
JournalIEEE Transactions on Computers
VolumeC-34
Issue number4
DOIs
StatePublished - Apr 1985

Keywords

  • Index Terms -Data compression
  • VLSI
  • VLSI complexity
  • lower bounds
  • minimum storage digital sorters
  • noncompressing sorting network
  • sorting network

ASJC Scopus subject areas

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

Fingerprint Dive into the research topics of 'Minimum storage sorting networks'. Together they form a unique fingerprint.

Cite this