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:
“Never is a historic deed already completed when it is done but always only when it is handed down to posterity. What we call “history” by no means represents the sum total of all significant deeds.... World history ... only comprises that tiny lighted sector which chanced to be placed in the spotlight by poetic or scholarly depictions.”
—Stefan Zweig (18811942)
“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)
“Make-believe is the avenue to much of the young child’s early understanding. He sorts out impressions and tries out ideas that are foundational to his later realistic comprehension. This private world sometimes is a quiet, solitary
world. More often it is a noisy, busy, crowded place where language grows, and social skills develop, and where perseverance and attention-span expand.”
—James L. Hymes, Jr. (20th century)