sorting of words in lexicographic order

Question

Given n words, is it possible to sort them in lexicographic order with o(n) time complexity?? Well i found a method like creating a trie data structure and an inorder traversal of the trie would result in time complexity close to O(kn) where k is the arbitrary string length, but the problem here being space complexity. constructing BST and inorder traversal is also a good option but time complexit is O(nlogn) . So could anyone suggest me whoch would be better BST or trie given the constraints of both. Any other algorithm or suggestions are also welcomed.

Answer 1

It is easy to sort the words in O(nL) time with a bucket sort or radix sort. Here L is word length. It's impossible to do better, since you must look at all the keys at least once.

Your triesort idea is an old one.