Sorting without exchanges on a bit-serial systolic array
Graham M. Megson · IEE Proceedings G Circuits Devices and Systems · 1990
In the paper, a number of bit-serial systolic designs for ordering a list of n elements without ‘on-the-fly’ exchanges are considered. The algorithms require 4n + p + k bit steps where p = log2n and k is the number of bits required to encode all the possible elements. The arrays require O(n(p + k)) bit cells with a complexity roughly the same as that of a full adder and between max (p, k) and p + k input/output pins. The input to the array is the list to be sorted and an auxiliary vector whose elements have bit length p. The output, is the list itself and the auxiliary vector, which is updated to produce pointers to the correct position of each element in the ordered list.