Multistage sorter having pushdown stacks for arranging an input list into numerical order

Claim 2

An M stage sorter for arranging input numbers into a numerically sorted output list, comprising: means for grouping the input numbers into groups; a first stage for ordering the input numbers within each of the groups, formed by a sorting stack which includes: stack input means for sequentially receiving all of the numbers within each of the groups; comparing means for comparing each currently received number to the previously received numbers from the same group; and stack storage means for inserting each currently received number into proper numerical order among the numbers previously received from the same group; M-1 subsequent stages for progressively forming fewer groups of more numbers each, the last stage of which forms the numerically sorted output list, each stage including: interstage storage means for storing the ordered groups from the preceding stage; stack input means for sequentially receiving each of the numbers stored in the interstage storage means; comparing means for comparing each currently received number to the previously received numbers currently in the sorting stack; pushdown storage means of inserting each currently received number into proper numerical order among the previously inserted numbers, which pushdown storage means progressively fills up from a first position to a last position as each currently received number is inserted; interstage output means for advancing the current number in the last position to the next stage; and pointer means for identifying the next-to-be received number from the interstage storage means which is the next number from the same group as the current number in the last position; and output means for receiving the ordered numbers from the last stage.

Claim 3

The sorter of claim 1, wherein M = 2.

Claim 4

The sorter of claim 1, wherein the input is N numbers and divided into Q groups of P numbers each.

Claim 5

The sorter of claim 3, wherein N = Q × P.

Claim 6

The sorter of claim 4, wherein P = Q √N for minimizing the circuitry required for sorting N input items.

Claim 7

The sorter of claim 1, wherein the comparing means displaces by one location in the pushdown storage means all the previously sorted numbers on one side of the insertion point to provide an empty location for the currently received number.

Claim 8

The sorter of claim 6, wherein the comparing means is a plurality of comparators, one associated with each location within the pushdown storage means, for determining whether each currently received number is less than or greater than each previously sorted number in the pushdown storage means.

Claim 9

The sorter of claim 7, wherein the plurality of comparators determine whether each new number is less than each previously sorted number or equal to or greater than each previously sorted number of causing the pushdown storage means to shift down by one location all previously sorted numbers which are less than the currently received number.

Claim 10

The sorter of claim 7, wherein the stack input means is a parallel input means permitting each new number to be presented simultaneously to the plurality of comparators.

Claim 11

The sorter of claim 6, wherein the sort stack is formed by a plurality of location elements E1, E2, E3 . . . . Ei . . . . En, each element comprising: a shift register Ri for holding one sorted item Bi; a comparator Ci for determining whether the currently received number A is less than or greater than the contents Bi of the shift register; and a gating circuit Gi responsive to the comparator Ci and to the comparator Gi-1 of the previous element Ei-1 for displacing the sorted item Bi to the next element Bi +1 and entering the new item A into register Ri when A is greater than or equal to Bi, and A is less than Bi-1.

Claim 12

The sorter of claim 1, wherein each of the N input numbers has a key portion which is arranged into numerical order by the sorter, and a nonkey portion.

Claim 13

The sorter of claim 11, wherein a nonkey storage means retains the nonkey portion, and a nonkey pointer means provides the nonkey storage address of each nonkey portion to the first stage.

Claim 14

The sorter of claim 12, wherein the nonkey pointer means includes a counter for generating the nonkey storage address.

Claim 15

A single stage multipass sorter for arranging input numbers into numerical order, comprising: grouping means for initially grouping the input numbers; a single sorting stack for initially ordering all of the numbers within each group formed by the grouping means to provide a first run of ordered groups, and for subsequently receiving the first number of each group in the first run to provide a second run with fewer groups of more numbers in each group, which is in turn sorted by the single stack until all of the groups have been merged into a single run, the single sorting stack comprising: stack input means for initially receiving in sequence all of the input numbers within each of the groups, and for subsequently receiving in sequence the first number in each group of a run; comparing means for initially comparing each currently received input number to the numbers previously received from the same group, and for subsequently comparing each currently received first number to the numbers previously received from the same run; and stack storage means having a sequence of locations for initially entering each currently received input number into proper numerical order within each group, and for subsequently entering each currently received first number into proper numerical order within the run then being formed, the stack storage means progressively filling from the first location to the last location as each currently received number is entered; an interpass storage means associated with each run for storing that run between passes by sequentially receiving the run numbers from the single sorting stack as they pass therethrough the last position therein; a pointer means associated with each interpass storage means for identifying the number next to be received by the single sorting stack from within the associated storage means which is the next number from the same group as the number currently in the last location of the single sort stack; and multiplexer means for initially selecting the grouping means as source of numbers into the single sorting stack, and for subsequently selecting each of the interpass storage means as the source of numbers into the single sorting stack.

Claim 16

A single stage multipass sorter for arranging input numbers into numerical order, comprising: grouping means for initially grouping the input numbers; a single sorting stack for initially ordering all of the numbers within each group formed by the grouping means to provide a first run of ordered groups, and for subsequently receiving the first number of each group in the first run to provide a second run with fewer groups of more numbers in each group, which is in turn sorted by the single stack until all of the groups have been merged into a single run, the single sorting stack comprising: stack input means for initially receiving in sequence all of the input numbers within each of the groups, and for subsequently receiving in sequence the first number in each group of a run; comparing means for initially comparing each currently received input number to the numbers previously received from the same group, and for subsequently comparing each currently received first number to the numbers previously received from the same run; and stack storage means having a sequence of locations for initially entering each currently received input number into proper numerical order within each group, and for subsequently entering each currently received first number into proper numerical order within the run then being formed, the stack storage means progressively filling from the first location to the last location as each currently received number is entered; an interpass storage means associated with each run for storing that run between passes by sequentially receiving the run numbers from the single sorting stack as they pass therethrough the last position therein; a pointer means associated with each interpass storage means for identifying the number next to be received by the single sorting stack from within the associated storage means which is the next number from the same group as the number currently in the last location of the single sort stack; and multiplexer means for initially selecting the grouping means as source of numbers into the single sorting stack, and for subsequently selecting each of the interpass storage means as the source of numbers into the single sorting stack.

Claim 17

the multipass sorter of claim 14, wherein the comparing means has S comparing elements and the stack storage means has S locations for merging S groups at a time causing the number of groups to decrease by a factor of S each pass and causing the size of each group to increase by a factor of S each pass.

Claim 18

The multipass sorter of claim 15, wherein the means for initially grouping the input numbers forms initial groups of s numbers each.

Claim 19

The multipass sorter of claim 16, wherein the number of input numbers is N and initially grouped into N/S initial groups.

Claim 20

The multipass sorter of claim 17 wherein each interpass storage means is a random access memory which reads to receive its run of N numbers as they are sorted by the single sorting stack, and which writes to supply the N numbers to the single sorting stack for sorting.

Claim 21

The multipass sorter of claim 18, wherein there is a first and second interpass storage means each of which alternatively reads and writes in opposition with the other to provide reading to and writing from the storage means.

Claim 22

The multipass sorter of claim 19, wherein the first interpass storage means reads during odd passes and writes during even passes, and the second interpass storage means reads during even passes and writes during odd passes.

Claim 23

The multipass sorter of claim 20, wherein the first and second interpass storage means each have a capacity of N.