# Digital Design: Is there an elegant way to put a number in a sorted register file?

Let's say we have a module that has a register file currently inside that can hold 3 numbers. Suppose the three numbers are: 4, 6, 7. 4 is at index 0, 6 is at index 1, and 7 is at index 2. A new number, 5, comes in. The module has 4 outputs, where the numbers are always sorted.

The obvious way to do this is to have three comparators in cascade. The number comes in, gets compared with the first number, the bigger one gets propagated and becomes one of the inputs to the next comparator, and so on.

The above solution works, but since the comparators are in cascade, the speed is dictated by how many elements we have inside the module. Also, I feel this method doesn't exploit the fact that the numbers are already in sorted order.

Another approach is to use a shift register. But this requires us to use a clock and also wait one clock cycle since registers get updated one clock cycle later. This is supposed to be a combinatorial circuit.

I was thinking of a third solution where we would compare the number with numbers in the module at once. This would give us something like 0, 1, 1. We could then use this as the inputs to a cascade of multiplexers to numbers. I'm not sure if this is faster than the comparator cascade structure I mentioned above.

Any better ideas are appreciated.

• basically, most, if not even all, the data structures thought in basic algorithms and data structures are representable in hardware, too. If you can build a heap... Jul 5 '20 at 19:19
• the speed is dictated by how many elements we have inside the module. yes, and that is inevitable. Jul 5 '20 at 19:20
• Try a binary search instead? Then you only have to go through O(log n) comparators instead of O(n). Jul 5 '20 at 19:20
• @MarcusMüller it's funny that you mentioned a heap. I'm actually implementing a head in hardware which takes only 1 clock cycle to enqueue a new element. The way I do it is represent each level of the queue in a separate BRAM. Then when a new element comes in, I find a path from a vacant space to the root node, generate the corresponding addresses of the BRAM based on this path, take the data from the BRAM, compare it with the new one, sort, and then write back to the BRAMs. That's why I was looking for a fast way to sort only a small section of the heap. Jul 5 '20 at 19:33
• @ChadWinters ah, interesting! I can't claim to have any expertise on the subject, but I think a term worth reading up on for you would be content-adressable memory. Jul 5 '20 at 19:43