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:
“For if the proper study of mankind is man, it is evidently more sensible to occupy yourself with the coherent, substantial and significant creatures of fiction than with the irrational and shadowy figures of real life.”
—W. Somerset Maugham (1874–1965)
“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)
“It’s all sorts of middle-aged white men in suits—forests of middle-aged men in dark suits. All slightly red-faced from eating and drinking too much.”
—Diane Abbott (b. 1953)