The algorithm boils down to two questions asked in parallel across all cells. For each cell, we must answer the questions:
- am I empty or occupied?
- If occupied, is my current value pushed by either the previous cell value or the new value to be sorted?
Simultaneously, each cell also needs the answer to both of these questions from the previous cell.
Hence, we can build a logical block designed for this specific purpose that answers these questions within a single clock cycle:
Afterwards, we can specify a parameter in the SystemVerilog source files that specify just how many of these cells we want for our particular application. A Sorter with N cells can sort lists of length up to length N in linear time!
For more details, and a full walkthrough of how these cells talk to each other as they sort new inputs, check out the step-by-step example on my webpage