Most Significant Digit Radix Sorts
A most significant digit (MSD) radix sort can be used to sort keys in lexicographic order. Unlike a least significant digit (LSD) radix sort, a most significant digit radix sort does not necessarily preserve the original order of duplicate keys. A MSD radix sort starts processing the keys from the most significant digit, leftmost digit, to the least significant digit, rightmost digit. This sequence is opposite that of least significant digit (LSD) radix sorts. An MSD radix sort stops rearranging the position of a key when the processing reaches a unique prefix of the key. Some MSD radix sorts use one level of buckets in which to group the keys. See the counting sort and pigeonhole sort articles. Other MSD radix sorts use multiple levels of buckets, which form a trie or a path in a trie. A postman's sort / postal sort is a kind of MSD radix sort.
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)
“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)