VLSI-sorting evaluated under the linear model (Q1117701)

The impact of basing evaluation of VLSI-sorting algorithms on the linear model is investigated. The main results of asymptotic analysis of sorting algorithms under the linear model are that the lower bounds allow \(AT^ 2\) optimal sorting algorithms only for \(T=\Theta(nk)\) but allow \(AP^ 2\) algorithms in the same range as under the constant model. Furthermore the sorting algorithms presented in the paper meet these lower bounds. For problem sizes that exceed realistic chip capacities, chip-external sorting algorithms can be used. The author presents two different such algorithms, BBB(S) and TWB(S). The formalism is correct and the exposition clear. Being at a high level of formality, the paper is intended for a few number of specialistis in computer science, those interested in computation complexity and parallel sorting algorithms.