| 摘要 |
An input list of N numbers is clocked through a first sort stage having S1 locations entered into an interstage memory as S2 groups of S1 numbers each. The S1 numbers in each group are in numerical order. The first number in each group forms an initial group of S2 numbers which necessarily includes the smallest number of the N input numbers. This initial group is loaded into a second sort stack having S2 locations which arranges the initial S2 numbers in numerical order. The smallest number forms the first number in the output list. A replacement number from the interstage memory is numerically sorted into the second stack each time the smallest remaining number is clocked out. This replacement number is the next number from the same group as the most recently clocked out number. Each new smallest remaining number must either be the second number in the second stack or the replacement number. In one embodiment two candidates exist for the next replacement number: (1) the next number from the same group as the current replacement number and (2) the next number from the same group as the second number. These candidates are addressed in advance of the current output determination to minimize the clock period. Alternatively, preaddressing may be accomplished by having an initial group of 256 numbers - the two smallest numbers in each of the S2 groups. There is only one candidate for the next replacement number, which candidate may be identified in advance.
|
