VLSI Sorting with Reduced Hardware
Joseph F. JáJá, Robert Michael Owens · IEEE Transactions on Computers · 1984
We propose a new VLSI architecture which allows many problems to be solved quite efficiently on chips with very small processing areas. We consider in detail the sorting problem and show how it can be solved quickly and elegantly on our model. We show that sorting n numbers can be done on a chip with processing area A = o(n) with an almost optimal speedup in a network with mesh-connected interconnections. The control is shown to be simple and easily implementable in VLSI.