MULTIPASS SORTER FOR ARRANGING AN INPUT LIST INTO NUMERICAL ORDER

摘要

An input list of N numbers is clocked through a first sort stack which provides S2 groups of S1 numbers each arranged in ascending numerical order. The numbers are stored in a buffer where the first location within each group always contains the smallest number in that group. These S2 first numbers are loaded into a second sort stack which arranges them in ascending numerical order. The first location in the second stack contains the smallest number in the entire list of N numbers. This smallest number is clocked out of the second stack to form the first number in the output list. A replacement number is numerically sorted into the second stack from the S2 groups each time the smallest remaining number is clocked out. This replacement number is the next smallest number from the same group as the most recently clocked out number. Each time the smallest remaining number is clocked out, the remaining numbers in the second stack are rearranged to accommodate the replacement number for maintaining numerical order. Thus the smallest remaining number whether from the second stack or from the buffer is always advanced to the first location of the second stack. Each stack includes a push-down shift register which contains already sorted numbers (B) at the top of the stack. Each new number (A) is compared to the sorted number (B) at each location. If the replacement number (A) is greater than the previously sorted number (B) at a particular stack location, the replacement number (A) is loaded into that location. The sorted numbers (B) at that location and all subsequent locations are simultaneously pushed down by one location. The input numbers (A) are thus sequentially inserted in numerical order into the stack of already sorted numbers (B).