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

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