The VLSI Complexity of Sorting

DOI10.1109/TC.1983.1676178zbMATH Open0524.68025OpenAlexW2134845208MaRDI QIDQ3036700FDOQ3036700

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)

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

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)