Hardware implementation of a tournament tree sort algorithm using an external memory

A computer program product for performing a tournament tree sort, comprising:

• a non-transitory computer readable storage medium having computer readable program code stored thereon that, when executed, causes a processor of a hardware accelerator to:
• receive a plurality of key values from a computer system;
• assign each of the plurality of key values a respective sequential key number as the plurality of key values are received, wherein each respective sequential key number is unique;
• perform a respective pairwise comparison of each pairing of key values assigned consecutive sequential key numbers as each pairing of key values is received to identify a respective winning key and a respective losing key for each respective pairwise comparison;
• store the respective losing key of each respective pairwise comparison in a first section of an external memory disposed on the hardware accelerator, wherein the respective losing key is stored at a physical location in the first section that is based on the respective sequential key number assigned to the respective losing key;
• store the respective winning key of each respective pairwise comparison in a second section of the external memory, wherein the respective winning key is stored at a physical location in the second section that is based on the respective sequential key number assigned to the respective winning key;
• perform subsequent pairwise comparisons of the winning keys and store a respective winning key of each subsequent pairwise comparison in a third section of the external memory, wherein the respective winning key of each subsequent pairwise comparison is stored at a physical location in the third section is based on the respective sequential key number assigned to the respective winning key of each subsequent pairwise comparison;
• receive a new key;
• reduce a number of accesses of the external memory by retrieving, from the external memory, only one key from each level of a tournament tree to reduce a total latency associated with accessing the external memory, wherein each retrieved key is a losing key stored in the first section of the external memory or a winning key stored in the second section of the external memory;
• and
• evaluate the new key for insertion into the tournament tree based on each retrieved key,
• wherein the first section of the external memory, the second section of the external memory, and the third section of the external memory correspond to different levels of the tournament tree, respectively, and wherein the processor of the hardware accelerator is one of a field programmable gate array or an application-specific integrated circuit.