Optimal Sorting Networks

Minimum comparator networks

While Bitonic and Odd-Even Merge produce correct sorting networks, they don't minimize the number of comparators. Bert Dobbelaere maintains a comprehensive database of the best-known sorting networks, many of which are provably optimal. For FPGA implementations, fewer comparators means less area and potentially lower latency.

Comparator Savings vs Bitonic Sort

SizeOptimal ComparatorsBitonic ComparatorsSavings
45617%
6121520%
8192421%
16608025%
View Optimal Networks Database

Resources