
related topics 
{math, number, function} 
{system, computer, user} 
{build, building, house} 
{@card@, make, design} 
{line, north, south} 
{rate, high, increase} 
{group, member, jewish} 
{mi², represent, 1st} 
{household, population, family} 

In computer science, radix sort is a sorting algorithm that sorts integers by processing individual digits, by comparing individual digits sharing the same significant position. A positional notation is required, but because integers can represent strings of characters (e.g., names or dates) and specially formatted floating point numbers, radix sort is not limited to integers. Radix sort dates back as far as 1887 to the work of Herman Hollerith on tabulating machines.^{[1]}
Most digital computers internally represent all of their data as electronic representations of binary numbers, so processing the digits of integer representations by groups of binary digit representations is most convenient. Two classifications of radix sorts are least significant digit (LSD) radix sorts and most significant digit (MSD) radix sorts. LSD radix sorts process the integer representations starting from the least significant digit and move towards the most significant digit. MSD radix sorts work the other way around.
The integer representations that are processed by sorting algorithms are often called "keys", which can exist all by themselves or be associated with other data. LSD radix sorts typically use the following sorting order: short keys come before longer keys, and keys of the same length are sorted lexicographically. This coincides with the normal order of integer representations, such as the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. MSD radix sorts use lexicographic order, which is suitable for sorting strings, such as words, or fixedlength integer representations. A sequence such as "b, c, d, e, f, g, h, i, j, ba" would be lexicographically sorted as "b, ba, c, d, e, f, g, h, i, j". If lexicographic ordering is used to sort variablelength integer representations, then the representations of the numbers from 1 to 10 would be output as 1, 10, 2, 3, 4, 5, 6, 7, 8, 9, as if the shorter keys were leftjustified and padded on the right with blank characters to make the shorter keys as long as the longest key for the purpose of determining sorted order.
Contents
Full article ▸


related documents 
Singular value decomposition 
Derivative 
Complex number 
Prime number 
Number 
Surreal number 
Eiffel (programming language) 
Common Lisp 
Regular expression 
Algorithm 
Quaternion 
Natural deduction 
Ordinal number 
Emmy Noether 
History of mathematics 
Distribution (mathematics) 
Smalltalk 
C++ 
Binary search algorithm 
Mandelbrot set 
Bernoulli number 
Computer numbering formats 
Field (mathematics) 
Forth (programming language) 
Linked list 
Fibonacci number 
Discrete Fourier transform 
Trigonometric functions 
Floating point 
Polynomial 
