Sorting without exchanges on a bit-serial systolic array

Abstract

The author considers, 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=log2 n 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.