Sorting binary numbers in hardware - A novel algorithm and its implementation

This paper describes a novel algorithm for sorting binary numbers in hardware, along with a custom VLSI hardware design for the same. For sorting n, k-bit binary numbers, our proposed algorithm takes O(n + 2 k) time. Sorting is performed by assigning relative ranks to the input numbers. A rank matrix of size n times n is used to store ranks. Each row of the rank matrix corresponds to one of the n numbers, and it stores a single non-zero entry. The position of this entry represents the relative rank of the corresponding number. In the worst case, our algorithm requires n+2 k clock cycles for assigning the final ranks. We start with a condition in which each number has an identical rank. In each of clock cycle, ranks are iteratively updated until the final ranks are determined after n+2 k clock cycles. The proposed algorithm is implemented in a 65 nm process, using a custom design approach to obtain a fast circuit. Our design is significantly faster than the fastest reported hardware sorting engine, with area performance which is superior for larger numbers.