Abstract

The grid-area required by a sorting net for input vectors of length N is shown to be at least (N - 1)²/2. Of all sorting nets which use o(N²) comparators, the bitonic sorting net of Batcher has been known to have a layout of O(N²), but the hidden constant factor has not been investigated. A straightforward use of known techniques leads to a layout of grid-area 20.25N². We present area-efficient layouts of the bitonic.