The VLSI Complexity of Sorting

DOI10.1109/TC.1983.1676178MaRDI QIDQ3036700zbMATH OpenOpenAlexFDO

Authors Clark D. Thompson

Publication date 1983

Published in IEEE Transactions on Computers (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/tc.1983.1676178

zbMATH Keywords

area-time complexitybitonic sortbubble sortheapsortmesh-connected computersparallel algorithmsshuffle exchange networksortingVLSI

Mathematics Subject Classification ID

Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68W99)

Cited in

(15)

• Improving the average delay of sorting
• Area-time lower-bound techniques with applications to sorting
• A minimum-area circuit for -selection
• Parallel ear decomposition search (EDS) and st-numbering in graphs
• Fault-tolerance VLSI sorters
• Time lower bounds for parallel sorting on a mesh-connected processor array
• VLSI-sorting evaluated under the linear model
• Running ASCEND, DESCEND and PIPELINE algorithms in parallel using small processors
• Functional inversion and communication complexity
• Parallel integer sorting using small operations
• New lower bound techniques for VLSI
• A parallel-design distributed-implementation (PDDI) general-purpose computer
• Finding Euler tours in parallel
• Constant time sorting on a processor array with a reconfigurable bus system
• The foundation of self-developing blob machines for spatial computing

This page was built for publication: The VLSI Complexity of Sorting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3036700)