マルチキークイックソート ================================================== 通常のソートアルゴリズムをそのまま文字列に適用すると，要素の比較に文字列長必要になる． たとえば通常のクイックソートで文字列長mのn個の文字列をソートすると :math:`O(mnlogn)` となる． マルチキークイックソートでは文字列の比較を先頭から一文字ずつ行っていく． ピボットとなる文字と比べて辞書順で小さいグループ，同じグループ，大きいグループの3つに分け， 同じグループでは次の位置の文字から，小さい・大きいグループでは同じ位置の文字からそれぞれ再帰的にソートを行う． ..　 todo:図 参考文献 ---------- * J.L.Bentley and R.Sedgewick. Fast algorithms for sorting and searching strings.In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms,pages 360-369, 1997