Radix sort with read-only key

摘要

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.

主权项

1. 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.