Back to results
US 12,306,776 B1Granted
Single-stage merge sorting method and apparatus
OwnerRobert Bernard Kentinventor
Life of this patent
Estimating the term…
Abstract
A method and apparatus for performing single-stage merge sorting of at least two pre-sorted input lists. The method and apparatus can provide a stable merge such that a value in an input list with a higher stable property will precede an equal value in another input list with a lower stable property when mapped into the single sorted output list. The method and apparatus preferably perform the merge sorting in a set of single-stage operations and are most preferably implemented in asynchronous combinatorial logic, which uses no internal clocking—although synchronously clocked operations can be used and will provide desirable results.
Claims19
A method for creating a stable single stage merging device, which merges numeric values of at least two pre-sorted input lists into a single sorted output list of the numeric values, the method comprising:
- establishing a ranking for the at least two pre-sorted input lists based on a position for each of the at least two pre-sorted input lists in a stable sort hierarchy, such that an equal value from a higher ranked input list of the at least two pre-sorted input lists always precedes an equal value from a lower ranked list of the at least two pre-sorted input lists in the single sorted output list;
- establishing a number of input ports of the stable single stage merging device equal to a sum total of a number of input values of the at least two pre-sorted input lists;
- establishing a number of output ports of the stable single stage merging device equal to the sum total of the number of input values of the at least two pre-sorted input lists;
- determining a set of cross-list comparisons in which each value in a higher-ranked list is compared by the stable single stage merging device to each value in each lower-ranked list using a Boolean comparison operation for greater-than-or-equal-to, such that a true comparison result indicates that a value from the higher ranked list is greater-than-or-equal-to a value from the lower ranked list;
- for each respective output port of the stable single stage merging device, determining a set of input ports of the stable single stage merging device that can map to that respective output port;
- for each respective output port of the stable single stage merging device, determining a set of comparisons that select a correct input port of the stable single stage merging device to map to that respective output port;
- determining all possible sorted output combinations of the input ports of the at least two pre-sorted input lists;
- for each respective output port of the stable single stage merging device, creating a conditional equation which uses the port's set of comparisons in order to map each of the output port's possible input values to that respective output port;
- for each respective output port of the stable single stage merging device, implementing a conditional equation which uses the port's set of comparisons acting as select lines for 2-to-1 multiplexers of the stable single stage merging device which map each of the output port's possible input values to that respective output port;
- and
- creating the stable single stage merging device in target hardware.
8 more elements
A method for creating a stable single stage merging device, which merges numeric values of at least two pre-sorted input lists into a single sorted output list of the numeric values, the method comprising:
- establishing a ranking for the at least two pre-sorted input lists based on a position for each of the at least two pre-sorted input lists in a stable sort hierarchy, such that an equal value from a higher ranked input list of the at least two pre-sorted input lists always precedes an equal value from a lower ranked list of the at least two pre-sorted input lists in the single sorted output list;
- establishing a number of input ports of the stable single stage merging device equal to a sum total of a number of input values of the at least two pre-sorted input lists;
- establishing a number of output ports of the stable single stage merging device equal to the sum total of the number of input values of the at least two pre-sorted input lists;
- determining a set of cross-list comparisons in which each value in a lower-ranked list is compared by the stable single stage merging device to each value in each higher-ranked list using a Boolean comparison operation, wherein a comparison result indicates that a value from the higher ranked list is greater-than-or-equal-to a value from the lower ranked list;
- for each respective output port of the stable single stage merging device, determining a set of input ports of the stable single stage merging device that can map to that respective output port;
- for each respective output port of the stable single stage merging device, determining a set of comparisons that select a correct input port of the stable single stage merging device to map to that respective output port;
- determining all possible sorted output combinations of the input ports of the at least two pre-sorted input lists;
- for each respective output port of the stable single stage merging device, creating a conditional equation which uses the port's set of comparisons in order to map each of the output port's possible input values to that respective output port;
- for each respective output port of the stable single stage merging device, implementing a conditional equation which uses the port's set of comparisons acting as select lines for 2-to-1 multiplexers of the stable single stage merging device which map each of the output port's possible input values to that respective output port;
- and
- creating the stable single stage merging device in target hardware.
8 more elements
Dependencies are inferred from the claim text.