MSD vs LSD radix sort

Question

I'm not sure why would one ever use LSD radix sort.

Advantages of MSD:

1. It can handle strings of variable length
2. It doesn't always need to scan the entire strings (it ca decide sooner about the order)
3. One can use insertion sort to circumvent the disadvantages of counting sort.

Answer 1

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. If you're sorting key/value pairs where the key is a string or an integer and you want to preserve the original relative ordering, LSD radix sort would be preferable over MSD radix sort.

Hope this helps!

Answer 2

@templatetypedef has summed it beautifully .
MSD radix sort is useful to sort keys in lexicographic order .
take a look at wikipedia for working examples and clearer info.

Answer 3

Biggest advantage of LSD radix sort for me is it speed because it is branch-free algorithm. It makes LSD radix sort fastest possible sort algorithm for relatively short fixed length keys. The stability of LSD is also nice feature.