Quicksort が遅い理由

クイックソートは、その性質上、再帰の最後の方になってくるとほとんど同じ要素同士を比較することになってしまうので、文字列配列の場合、最後の方の比較のコストがかなり大きくなってしまうので、それが影響しているのではないかと。

む。そうかも。
まぁ、なんにしても Multikey Quicksort が結構速いっすね。いや MSD Radix Sort も同じぐらいの性能が出るけど。
つうか、一口に文字列ソートといっても、どんなデータをソートするかによるわけだけど。DNA の塩基配列なんかだと MSD Radix Sort のが強いかも。