文字列ソーティング

Algorithm

文字列をソートするのに、クイックソート系のアルゴリズムをつかうのと、マージソート系のアルゴリズムを使うのでは、効率が大分変わる。
と思うのだけれど、マージソート系で文字列ソートを速くする方法ってあるのかな？

んーアルゴリズム的にはどちらも O(n log n)だったと思うし、 「効率がだいぶ変わる」というのは一体?

文字列の比較コストはコンスタントじゃないですからね。マージソートならマージの時に辞書的に近い位置の文字列ばかりを比較することになるから、比較コストが大きくなるってことなんじゃないでしょうか。
まぁ、データによるんでしょうけど、Suffix Array の構築とかになると結構違ってくるかもしれません。
ちなみに、文字列ソーティングに強いクイックソートなら Multikey Quicksort ってのがあります。