| 摘要 |
This invention describes a pipeline sorter, in which record-pairs are compared and conditionally swapped while being advanced along the pipeline synchronously. The pipeline sorter has the topology of a U-shaped tube, with regularly spaced crosspaths linking the two arms. Records are loaded one at a time, into the input arm synchronously, and emerge out of the output arm, also one at a time and synchronously. Within the sorter, at periodic time intervals a number of record-pairs at correlated positions of the U-tube are compared. Dependent on the comparison outcome, either the original records themselves, moving along vertical paths, or their permutation, moving along crosspaths, will arrive at the next down-stream positions. In this manner, as soon as the last record has been loaded, the correctly sorted output will begin to emerge, with the overall sorting time completely overlapped by the loading and unloading of records.
|
