Layout of the Batcher bitonic sorter

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 sorter. First, we describe a flip-bitonic sorting net - it is isomorphic to Batcher's bitonic sorter but leads naturally to a layout of grid-area less than 4N². Second, we present a butterfly-based layout of the bitonic sorter with grid-area of 3N² + O(N). The former does not use knock-knees while the latter relies on them and is more compact.