Sorting a list of names lexographically

Question

Say you are given a list of names, S = {s1, s2 ... sn} and you want to sort them lexicographically.

How would you guarantee that the running time of the sort is O(the total sum of the lengths of all the words)?

Any useful techniques?

Answer 1

One simple solution would be to use MSD radix sort, assuming a constant-size alphabet. Replace "digit" by "character" while reading the algorithm description. You will also need to throw out strings that are smaller than i if you are currently processing the position i, otherwise you won't get the desired runtime.