Multistage sorter having pushdown stacks for arranging an input

Details Multistage sorter having pushdown stacks for arranging an input Multistage sorter having pushdown stacks for arranging an input

1975-10-16

1977-06-14

Chapnick, Melvin B.

Communications: electrical

Digital comparator systems

G06F 724

Patent

active

040300773

ABSTRACT:
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).

REFERENCES:
patent: 2901732 (1959-08-01), Canning
patent: 2985864 (1961-05-01), Fillebrown et al.
patent: 2987705 (1961-06-01), Van Mechelen
patent: 3029413 (1962-04-01), O'Connor et al.
patent: 3234524 (1966-02-01), Roth
patent: 3242466 (1966-03-01), Dirks
patent: 3380029 (1968-04-01), Goetz
patent: 3428946 (1969-02-01), Batcher
patent: 3540000 (1970-11-01), Bencher
patent: 3740538 (1973-06-01), Hemphill
patent: 3775753 (1973-11-01), Kastner
H. Nagler, "Amphisbaenic Sorting" in Journal of Association for Computing Machinery, Oct. 1959, pp. 459-468.
M. A. Goetz, "Some Improvements in the Tech. of String Merging & Internal Sorting" in Proceedings-Spring Joint Computer Conf., 1964; pp. 599-607.

Affiliated with

Also associated with

Rating

Multistage sorter having pushdown stacks for arranging an input does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Multistage sorter having pushdown stacks for arranging an input , we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multistage sorter having pushdown stacks for arranging an input will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-13479