Layout of the batcher bitonic sorter (extended abstract)
Shimon Even, S. Muthukrishnan, Michael Stewart Paterson, Süleyman Cenk Şahinalp · 1998
The grid-area required by a sorting net for input vectors of length N is shown to be at least (N -1)"/2.Of 11 a sorting nets which use o(N2) 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.25N2.We present area-efficient layouts of the bitonic