Back to results
US 9,177,006 B2Granted
Radix sort with read-only key
AssigneeInternational Business Machines Corporation
InventorsSameh W. Asaad, Hong Min, Bharat Sukhwani, Mathew S. Thoennes
Life of this patent
Estimating the term…
Abstract
Methods and arrangements for a radix sort with a read only key. A plurality of keys are received, an array and a link table are populated for the first digit of the keys based upon the keys; and an array and a link table are populated for each successive digit of the keys based upon the array and link table populated for the preceding digit of the keys. Embodiments may be implemented in both hardware (FPGAs, ASICs, information handling devices, etc.) and software. Other embodiments are also disclosed and claimed.
Claims17
An apparatus for implementing a radix sort, the apparatus comprising:
- one or more processors;
- and
- a memory operatively coupled to the one or more processors that stores instructions executable by the one or more processors to perform acts comprising:
- receiving a plurality of keys to be sorted in a radix sort;
- populating a first array and a first link list for a first digit of the keys based upon the keys, the first array comprising a first head array and a first tail array, wherein the first head array stores an initial value of the first link list and the first tail array stores an end value of the first link list;
- populating an array and a link list for each successive digit of the keys based upon the array and link list populated for the preceding digit of the keys, the array comprising a head array and a tail array, wherein the head array stores an initial value of the link list and the tail array stores an end value of the link list;
- and
- producing a final radix sort of the keys based on a final array and a final link list populated for the final digit of the keys;
- wherein the array stores a portion of the link list values associated with each successive digit.
6 more elements
An apparatus comprising:
- at least one programmable logic device (PLD) containing programmable circuit elements;
- said programmable circuit elements being configured to:
- receive a plurality of keys to be sorted in a radix sort;
- populate a first array and a first link list for the first digit of the keys based upon the keys, the first array comprising a first head array and a first tail array, wherein the first head array stores an initial value of the first link list and the first tail array stores an end value of the first link list;
- populate an array and a link list for each successive digit of the keys based upon the array and link list populated for the preceding digit of the keys, the array comprising a head array and a tail array, wherein the head array stores an initial value of the link list and the tail array stores an end value of the link list;
- and
- produce a final radix sort of the keys based on a final array and a final link list populated for the final digit of the keys;
- wherein the array stores a portion of the link list values associated with each successive digit.
5 more elements
A computer program product comprising:
- a computer readable storage medium having computer readable program code embodied therewith, the computer readable program code comprising:
- computer readable program code configured to receive a plurality of keys to be sorted in a radix sort;
- computer readable program code configured to populate a first array and a first link list for the first digit of the keys based upon the keys, the first array comprising a first head array and a first tail array, wherein the first head array stores an initial value of the first link list and the first tail array stores an end value of the first link list;
- computer readable program code configured to populate an array and a link list for each successive digit of the keys based upon the array and link list populated for the preceding digit of the keys, the array comprising a head array and a tail array, wherein the head array stores an initial value of the link list and the tail array stores an end value of the link list;
- and
- computer readable program code configured to produce a final radix sort of the keys based on a final array and a final link list populated for the final digit of the keys;
- wherein the array stores a portion of the link list values associated with each successive digit.
4 more elements
Dependencies are inferred from the claim text.