Least Significant Digit Radix Sorts
A least significant digit (LSD) radix sort is a fast stable sorting algorithm which can be used to sort keys in integer representation order. Keys may be a string of characters, or numerical digits in a given 'radix'. The processing of the keys begins at the least significant digit (i.e., the rightmost digit), and proceeds to the most significant digit (i.e., the leftmost digit). The sequence in which digits are processed by a LSD radix sort is the opposite of the sequence in which digits are processed by a most significant digit (MSD) radix sort.
An LSD radix sort operates in O(nk) time, where n is the number of keys, and k is the average key length. This kind of performance for variable-length keys can be achieved by grouping all of the keys that have the same length together and separately performing an LSD radix sort on each group of keys for each length, from shortest to longest, in order to avoid processing the whole list of keys on every sorting pass.
A radix sorting algorithm was originally used to sort punched cards in several passes. A computer algorithm was invented for radix sort in 1954 at MIT by Harold H. Seward. In many large applications needing speed, the computer radix sort is an improvement on (slower) comparison sorts.
LSD radix sorts have resurfaced as an alternative to high performance comparison-based sorting algorithms (like heapsort and mergesort) that require Ω(n · log n) comparisons, where n is the number of items to be sorted. Comparison sorts can do no better than Ω(n · log n) execution time but offer the flexibility of being able to sort with respect to more complicated orderings than a lexicographic one; however, this ability is of little importance in many practical applications.
Read more about this topic: Radix Sort
Famous quotes containing the words significant, digit and/or sorts:
“One of the most significant effects of age-segregation in our society has been the isolation of children from the world of work. Whereas in the past children not only saw what their parents did for a living but even shared substantially in the task, many children nowadays have only a vague notion of the nature of the parent’s job, and have had little or no opportunity to observe the parent, or for that matter any other adult, when he is fully engaged in his work.”
—Urie Bronfenbrenner (b. 1917)
“Bless my soul, Sir, will you Britons not credit that an American can be a gentleman, & have read the Waverly Novels, tho every digit may have been in the tar-bucket?”
—Herman Melville (1819–1891)
“I may be old-fashioned. I don’t like this modern movement.... And yet, there are certain sorts of work a woman may well do; teaching, being governess, or any taking care of children.”
—Julia Dent Grant (1826–1902)