Dual reciprocating pipelined sorter

Abstract

The invention is a bidirectional transposition exchange sorter for performing two overlapped sort operations overlapped in time with input/output operations so as to consume zero time. The sorter operates on the basis of a stack of cells, each of which contains two item storage locations and a comparator. The cells are arranged in a sorter stack configuration with a shift register monitor for each cell and an extra shift register position at the top of the sorter stack and also at the bottom. The monitor carries an indication of the current transfer mode for the cell. Each sort is carried out as two semi-sorts, input and output, which semi-sorts are time overlapped with the input and output operations typical of sort operations in computers. A portion of the sort operation takes place during an input step, so as to result in a partial reconfiguration of an unordered sequence at the end of the input semi-sort. Thereafter, a second portion of the sort operation takes place; the items exit in fully ordered sequence. After the sorter stack has been loaded with a first semi-sort of an unordered sequence, for example at the top end of the sorter stack, the second semi-sort of the unordered sequence at the top end may be overlapped with a first semi-sort of another unordered group of items being presented at the bottom end of the sorter stack.