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:
“As between these two, the need that in its haste to be abolished cannot pause to be stated and the need that is the absolute predicament of particular human identity, one does not presume to suggest a relation of worth. Yet the distinction is perhaps not idle, for it is from the failure to make it that proceeds the common rejection as “obscure” of most that is significant in modern music, painting and literature.”
—Samuel Beckett (1906–1989)
“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)
“There are several sorts of curiosity: a curiosity of self-interest, for example, which makes us desire to learn things that may be useful to us; and one of pride, which proceeds from an itch to know more than other people.”
—François, Duc De La Rochefoucauld (1613–1680)