Integer sorting

In computer science, integer sorting is the algorithmic problem of sorting a collection of data values by integer keys. Algorithms designed for integer sorting may also often be applied to sorting problems in which the keys are floating point numbers, rational numbers, or text strings. The ability to perform integer arithmetic on the keys allows integer sorting algorithms to be faster than comparison sorting algorithms in many cases, depending on the details of which operations are allowed in the model of computing and how large the integers to be sorted are. Integer sorting algorithms including pigeonhole sort, counting sort, and radix sort are widely used and practical. 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. Many such algorithms are known, with performance depending on a combination of the number of items to be sorted, number of bits per key, and number of bits per word of the computer performing the sorting algorithm. Time bounds for integer sorting algorithms typically depend on three parameters: the number n of data values to be sorted, the magnitude K of the largest possible key to be sorted, and the number w of bits that can be represented in a single machine word of the computer on which the algorithm is to be performed. Typically, it is assumed that w ≥ log2(max(n, K)); that is, that machine words are large enough to represent an index into the sequence of input data, and also large enough to represent a single key. Integer sorting algorithms are usually designed to work in either the pointer machine or random access machine models of computing. The main difference between these two models is in how memory may be addressed. The random access machine allows any value that is stored in a register to be used as the address of memory read and write operations, with unit cost per operation. This ability allows certain complex operations on data to be implemented quickly using table lookups.