Sorting strings using Counting Sort in O(n), where n is the total number of characters in all the strings
Here is the general idea:


Sort all the strings according to their first character (refer to each string using an index to save time).
Partition the strings according to their first character, and run recursively on each part (deleting in your mind the first character).


I'll let you work out the details.