Other integer sorting algorithms with smaller worst-case time bounds are not believed to be practical for computer architectures with 64 or fewer bits per word.
[4] Andersson, Miltersen & Thorup (1999) showed that in some cases the multiplications or table lookups required by some integer sorting algorithms could be replaced by customized operations that would be more easily implemented in hardware but that are not typically available on general-purpose computers.
Thorup (2003) improved on this by showing how to replace these special operations by the bit field manipulation instructions already available on Pentium processors.
[8] Much of the subsequent research on integer sorting algorithms has focused less on practicality and more on theoretical improvements in their worst case analysis, and the algorithms that come from this line of research are not believed to be practical for current 64-bit computer architectures, although experiments have shown that some of these methods may be an improvement on radix sorting for data with 128 or more bits per key.
Then, a prefix sum computation is used to determine the range of positions in the sorted output at which the values with each key should be placed.
However, despite their theoretical advantages, these algorithms are not an improvement for the typical ranges of these parameters that arise in practical sorting problems.
Another priority queue with similar performance (including the need for randomization in the form of hash tables) is the Y-fast trie of Willard (1983).
They then group the items to be sorted into buckets according to their high digits, in linear time, using either a large but uninitialized direct addressed memory or a hash table.
Repeating this range reduction until the keys are small enough to bucket sort leads to an algorithm with running time O(n log logn K).
A complicated randomized algorithm of Han & Thorup (2002) in the word RAM model of computation allows these time bounds to be reduced even farther, to O(n√log log K).
An integer sorting algorithm is said to be non-conservative if it requires a word size w that is significantly larger than log max(n, K).
However, when the key size or the word size is very large relative to the number of items (or equivalently when the number of items is small), it may again become possible to sort quickly, using different algorithms that take advantage of the parallelism inherent in the ability to perform arithmetic operations on large words.
Building on their work, Fredman & Willard (1994) described two data structures, the Q-heap and the atomic heap, that are implementable on a random access machine.
The Q-heap is a bit-parallel version of a binary trie, and allows both priority queue operations and successor and predecessor queries to be performed in constant time for sets of O((log N)1/4) items, where N ≤ 2w is the size of the precomputed tables needed to implement the data structure.
The atomic heap is a B-tree in which each tree node is represented as a Q-heap; it allows constant time priority queue operations (and therefore sorting) for sets of (log N)O(1) items.
As in the algorithm of Kirkpatrick and Reisch, they perform range reduction using a representation of the keys as numbers in base b for a careful choice of b.
For instance, by repeatedly applying the Kirkpatrick–Reisch range reduction technique until the keys are small enough to apply the Albers–Hagerup packed sorting algorithm, it is possible to sort in time O(n log log n); however, the range reduction part of this algorithm requires either a large memory (proportional to √K) or randomization in the form of hash tables.