Publication | Closed Access
Shear Sort: A True Two-Dimensional Sorting Techniques for VLSI Networks.
50
Citations
0
References
1986
Year
Overall Sorted SequenceData MovementComputational ScienceArray ComputingEngineeringNetwork AlgorithmVlsi ArchitectureSorting AlgorithmComputer EngineeringComputer ArchitectureNetwork AnalysisComputational ComplexityExternal-memory AlgorithmOrder-sorted LogicComputer ScienceParallel ComputingShear SortRow-column Sorting Technique
Given a sequence of numbers which can be mapped into an m x n array, the sorting of rows and columns is shown to yield an overall sorted sequence. This unusually simple procedure is proven to require O(log2m) iterations by analyzing the data movement in the array under successive row and column sorts. An efficient bubble sort network suitable for VLSI implementation with near-optimal area-time-squared performance is a direct application of the row-column sorting technique.