Menu
The book "Introduction to Algorithms" mentions about the LSD (Least Significant Digit) version of radix sort. However , as others have pointed out here in stackoverflow, a MSD (Most Significant Digit) version also exists. So I want to know the pros and cons of each of these. My guess is that the LSD version has some benefits over the MSD one but I am not sure. Hence the question.
365
LSD is faster than MSD when there is a fixed length. MSD is too slow for small files, and it need huge number of recursive calls on small files.
One advantage of LSD radix sort over MSD radix sort is that LSD radix sort is a stable sort - if there are multiple elements to sort with the same key, they'll end up in the same relative order in the sorted output when you run LSD radix sort, but might not if you run MSD radix sort.
Explanation: MSD stands for Most Significant Digit. It is named so because in this algorithm the processing begins from the most significant digit. 3. Which of the following combines qualities of MSD radix sort and LSD radix sort?
Taken from the link, might be useful: http://www.eternallyconfuzzled.com/tuts/algorithms/jsw_tut_sorting.aspx (At the very bottom)
The biggest problem with LSD radix sort is that it starts at the digits that make the least difference. If we could start with the most significant digits, the first pass would go a long way toward sorting the entire range, and each pass after that would simply handle the details. The idea of MSD radix sorting is to divide all of the digits with an equal value into their own bucket, then do the same thing with all of the buckets until the array is sorted. Naturally, this suggests a recursive algorithm, but it also means that we can now sort variable length items and we don't have to touch all of the digits to get a sorted array. This makes MSD radix sort considerably faster and more useful.
101
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
