A Minimum Area VLSI Network for O(log n) Time Sorting

A generalization of a known class of parallel sorting algorithms is presented, together with a new interconnection to execute them. A VLSI implementation is also proposed, and its area-time performance is discussed. It is shown that an algorithm in the class is executable in O(log n) time by a chip occupying O(n²) area. The design is a typical instance of a ``hybrid architecture,´´ resulting from the combination of well-known VLSI networks as the orthogonal trees and the cube-connected cycles; it also provably meets the AT² = ¿(n² log² n) lower bound for sorters of n words of length (1 + ¿) log n (¿ ≫ 0).