Area efficient layouts of the Batcher sorting networks

In the early 1980s, the grid area required by the sorting nets of Batcher for input vectors of length N was investigated by Thompson. He showed that the Omega (N-2) area was necessary and sufficient, but the hidden constant factors, both for the lower and upper bounds, were not discussed. In this paper, a lower bound of (N - 1)(2)/2 is proven, for the area required by any sorting network. Upper bounds of 4N(2) and 3N(2) are shown for the bitonic sorter and the odd-even sorter, respectively. In the layouts, which are presented to establish these upper bounds, slanted lines are used and there are no knock-knees. (C) 2001 John Wiley & Sons, Inc.