Sorting N items using a p-sorter in optimal time
S. Olarin, S. Q. Zheng · 2002
A sorting device capable of sorting p items in constant time is called a p-sorter. It is known that the task of sorting N items using a p-sorter requires at least /spl Omega/ (N log N/p log p) applications of the p-sorter. This bound is tight: there exist algorithms that use O (N log N/p log p) calls to the p-sorter to sort N items. However, there is no known implementable algorithm that can sort N items in O(N log N/p log p) time using a p-sorter. The main contribution of this paper is to propose a simple VLSI architecture and to show that in our architecture N items can be sorted in O(N log N/p log p) calls to the p-sorter, while enforcing conflict-free memory accesses. An important feature of our design is that the total additional VLSI area for hardware, other than the memory for data and the p-sorter, is kept to a minimum.