The VLSI Complexity of Sorting

DOI10.1109/TC.1983.1676178zbMath0524.68025OpenAlexW2134845208MaRDI QIDQ3036700

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

sortingparallel algorithmsVLSIarea-time complexityheapsortbubble 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)

Related Items (15)

Functional inversion and communication complexity ⋮ Area-time lower-bound techniques with applications to sorting ⋮ A minimum-area circuit for \(\ell\)-selection ⋮ Parallel integer sorting using small operations ⋮ 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 ⋮ Constant time sorting on a processor array with a reconfigurable bus system ⋮ The foundation of self-developing blob machines for spatial computing ⋮ Running ASCEND, DESCEND and PIPELINE algorithms in parallel using small processors ⋮ Improving the average delay of sorting ⋮ A parallel-design distributed-implementation (PDDI) general-purpose computer ⋮ Finding Euler tours in parallel ⋮ New lower bound techniques for VLSI

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