## Abstract

The grid-area required by a sorting net for input vectors of length N is shown to be at least (N - 1)^{2}/2. Of all sorting nets which use o(N^{2}) comparators, the bitonic sorting net of Batcher has been known to have a layout of O(N^{2}), but the hidden constant factor has not been investigated. A straightforward use of known techniques leads to a layout of grid-area 20.25N^{2}. 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^{2}. Second, we present a butterfly-based layout of the bitonic sorter with grid-area of 3N^{2} + O(N). The former does not use knock-knees while the latter relies on them and is more compact.

Original language | English (US) |
---|---|

Pages | 172-181 |

Number of pages | 10 |

State | Published - Jan 1 1998 |

Externally published | Yes |

Event | Proceedings of the 1998 10th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA - Puerto Vallarta, Mexico Duration: Jun 28 1998 → Jul 2 1998 |

### Other

Other | Proceedings of the 1998 10th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA |
---|---|

City | Puerto Vallarta, Mexico |

Period | 6/28/98 → 7/2/98 |

## All Science Journal Classification (ASJC) codes

- Software
- Safety, Risk, Reliability and Quality