FPGA Algorithms

Hardware sorting networks and parallel algorithms

Sorting networks are comparison-based sorting algorithms with a fixed sequence of comparisons. Unlike software sorting algorithms that make data-dependent decisions, sorting networks perform the same comparisons regardless of input data, making them ideal for hardware implementation in FPGAs where parallel comparisons can execute simultaneously.

Sorting Networks

Bitonic Sort

Recursive bitonic sequences with regular structure ideal for parallel hardware.

Odd-Even Merge Sort

Batcher's classic algorithm with elegant odd-even merging structure.

Optimal Sorting Networks

Minimum comparator networks from Bert Dobbelaere's research.

Streaming Sort

FIFO 1→2 FIFO 2→4 FIFO 4→8

Streaming Merge Sort

Pipelined merge tree with 1 elem/cycle throughput for large streaming datasets.

Median Networks

Optimal Median Networks

Find the median without full sorting. Essential for FPGA image processing and noise reduction.

Resources