Radix sorting strings

Question

This week, we learned all different kinds of sorts. The Efficiency of Radix Sort is amazing. however; it is limited to certain data. I am wondering if it can work with Strings. For example, "Monday","Friday" and "Sunday" are my data-set. Does anyone know how to sort them using Radix sort ? or any one has seen any article about sorting String using Radix, share it with me.

Answer 1

Yes, strings can be sorted with radix sort. In fact, radix sort is extremely effective on strings!

Given a collection of strings, you can radix sort them by first sorting the strings by their first letter (use any sorting algorithm you'd like, like counting sort or even insertion sort), breaking the strings into groups by their first letter, then recursively sorting all of the strings in each group. (This would be a most-significant-digit radix sort). You could also do a least-significant-digit radix sort. Imagine that all strings are padded up to the length of the maximum string with some special character ❤ that lexicographically precedes all the other characters. Then just do a regular LSD radix sort. When you're done, everything will be in sorted order!