对仅包含 a-z 和空格的单词数组进行排序的最快方法是什么？

我想知道是否有比快速排序/合并排序更快的方法来对此类数组进行排序。

数组的最大长度为 10^6。 单词的长度 >=10 且

您可以将所有单词放在一个trie http://en.wikipedia.org/wiki/Trie (or a 基数树 http://en.wikipedia.org/wiki/Radix_tree），然后将其打印在DFS http://en.wikipedia.org/wiki/Depth-first_search顺序，从 DFS 中每个级别的“较小”词典字母开始。

该解决方案将是O(n* |S|) where |S|是平均字符串长度。

简单的例子：

设字符串集合为[ac,ab,aca]:

结果特里将是：

         a
       /  \
      /    \
     b      c
     |     / \
     $    $   a
              |
              $

以及 DFS（更喜欢字典顺序上较小的字符）：DFS 将从a, go to b，然后到结束标志（$）并首先打印ab，然后返回a，并且有权c，并到下一个$签名，并将打印ac，以及旁边a和它的$并将打印aca，导致打印：

ab
ac
aca

正如预期的那样。