Sort circuit and method using multiple parallel sorts of the sorted items

Abstract

Abstract In a sort circuit comprised of m sort stages, the sort stages perform respective sorts, in parallel, on each input word as it is received. In particular, in the j th one of the stages, j=1,2, . . . m, a bit is associated with each different possible pattern of the values of the D j highest-order digits in the input word, D 1 >D 2 > . . . D m . As each input word is received, the values of its D j higher-order digits are examined and the associated bit is set. During output processing, the j th stage of the sort circuit receives from the (j+1) st stage a D j+1 -digit pattern representing the D j+1 highest-order digits of a word or words previously input to the sort circuit. The D j+1 -digit pattern is used to identify the bits within the j th stage associated with the D j -digit patterns whose D j+1 highest-order digits match the input pattern. The bits thus identified are processed within the j th stage using priority logic circuitry so as to provide the D j -digit patterns associated with the ones of the identified bits which are set. These D j -digit patterns are provided to the (j-1) st stage as its input digit pattern or, in the case of j=1, to the utilizing system. When the j th stage has processed all of the bits identified in response to a particular D j+1 -digit pattern, it requests a new pattern from the (j+1) st stage.

Inventors

• 👤 Harold G. Alles

Bibliographic Details