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

parallel algorithmssortingVLSIheapsortarea-time complexitybubble sortmesh-connected computersbitonic sortshuffle exchange network

Mathematics Subject Classification ID

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

Cited in

(15)

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