An initial input list in a series of sequential dependent input lists is clocked through a first sort stack and written into a first buffer as Q groups of P numbers each. The P numbers are in numerical order within each group with the smallest number in the first location of each group. The first number in each group is loaded into a second sort stack which arranges them in numerical order, causing the smallest number in the input list to form the first number in the initial output list. A replacement number is numerically sorted into the second stack from the Q groups each time the smallest remaining number is clocked out. Each replacement number is from the next location of the same Q group as the most recently clocked out number. Thus, the smallest remaining number in any of the Q groups of the first buffer is always available to the second stack and appears as the smallest remaining number in the second stack is always in the first location of the second stack. As the contents of the first buffer are inserted in to the second stack, the first sort stack processes a next input list into a second buffer. The buffers read and write in overlap manner permitting both sort stacks to process input lists simultaneously. As each smallest remaining number of the initial list becomes available at the output of the second stack, it may be updated and returned to the input of the first stack as an element of the subsequent dependent list. The double buffer overlap operation approximately doubles the throughput rate and permits updating of the dependent lists.
Record data on a disk file is sorted in a text/data processor by means of an algorithm that transfers such records on the basis of rank to a sort buffer on the basis of qualifying criteria. Each qualified file record is compared with the lowest ranked record previously transferred and located in the sort buffer. When a higher ranked record is identified it is transferred into the buffer at a location based on qualification. Lower ranked records are deleted from the sort buffer if space does not permit the storing of such records within the space available. When the sort buffer has been loaded with the highest ranked records remaining in the disk file without overflowing the buffer is unloaded to an output device. The sort program recycles through a subsequent pass again transferring the highest ranked remaining records into the sort buffer. To minimize recycle time, a presort algorithm is run to set record identifying bits in a bit map section of the sort buffer. Each time the contents of the sort buffer is output the record identifying bits for the records in the sort buffer are reset to a second state. The second state of a record identifying bit indicates that that record will not be considered for future passes through the sort routine.
A document sorting process utilizes existing or natural incoming sequences of documents each of which includes a sort key code thereon and which are sequentially arranged in accordance with a trace, locate and retrieve number (TLR). The documents are machine-sorted by the sort key code in numerical sequence and the corresponding trace, locate and retrieve number is checked for ascending or descending order. Whenever the trace, locate and retrieve number is seen in ascending order, the created sort number remains the same, whereas on a descending record the sort number is incremented by one digit. A reduction in the number of sort numbers reduces the passes required for physically sorting the documents.
A sorting arrangement such as in a pattern recognizer employs a memory having N data storage locations. The same extreme value data signal is initially placed in each location. The memory locations are partitioned into two or more sections. A sequence of input signals having values other than the extreme value are received. The value of the current input signal is compared to the values of the data signals in the first section to determine a position for the input signal among the memory locations while, concurrently, the immediately preceding input signal is compared to the values of the data signals of the second section to determine a position for the immediately preceding input signal in the memory locations. The sorting is speeded up by the input signal overlap.
Operating at real-time data rates, the disclosed hardware network generates a signal which closely approximates the Mth-largest of a set of R input data signals. The operational basis of this network is a comparison (121-127) between the input data (101-107) and a monotonically-scanning reference function (110). At that point (140, 150, 160) when the lower (R-M+1) of the inputs have been equaled by an increasing reference, the reference has become the same as the Mth-largest and is used (119b, 165, 170, 175) as the filter output. Analogous operation is achieved with a decreasing reference. When the number R of inputs is odd and M is made equal to ((R+1)/2), the network becomes a real-time median filter.
Operating at real-time data rates, hardware logic networks (FIGS. 3-6) receive onto a data-channel array (390 in FIG. 3) a set of unordered input data values and iteratively pair-wise transpose the set members until their positional order on the array coincides with the order the members would assume if their magnitudes were arranged according to sequential ordinal rank. Pair-wise comparisons between the data values themselves provide the basis for the mechanized pair-wise transposition schemes. Within each network, a key building block for performing both the pair comparisons and member transpositions is a Number Pair Orderer (NPO) (FIG. 2). Each NPO compares (210) two data elements and passes the smaller to one of its outputs (240), while passing the larger to the other of its outputs (260). Individual NPO's are arranged into two groups (311-315 and 321-325), each of which operates iteratively upon pairs of substantially all of the data values. The data-channel array, mechanized in a recirculatory configuration, carries the data back and forth between the two NPO groups. By making the pairs ordered by one NPO group mutually offset from the pairs ordered by the other group, a pair-to-pair transfer of unordered data elements to array positions beyond adjacent channels is accomplished. The recirculatory pair-wise ordering action is complete when the data has passed through the alternate NPO groups a sufficient number of times to enable a maximally-unordered set to be transposed into proper sequence. The networks become real-time median filters when configured to receive an odd number R of inputs and the ((R+1)/2)nd-largest member of the final ordered set is selected as the overall network output.
