Patent ID: 7363304

Claim:
A system for sorting a number of items in a computer system, the sort being based on a plurality of values of a key, each item having a value of the plurality of values, the system comprising: a plurality of stages, each stage having first and second first-in-first-out buffers (FIFOs), the FIFOs in each stage storing twice as many of the items as the FIFOs in a previous stage of the plurality of stages; at least one switch, each of the at least one switch coupled between two successive stages of the plurality of stages, each switch operable to merge and sort items stored in the pair of FIFOs in the previous stage based on the key to produce a sorted set of items, each of the at least one switch operable to provide successive sets of sorted items alternately to the first and second FIFOs in the next stage; and a final switch coupled to a last stage of the plurality of stages, the final switch operable to merge and sort the items stored in the pair of FIFOs in the last stage to provide the number of items in order.