マルチキークイックソート

通常のソートアルゴリズムをそのまま文字列に適用すると，要素の比較に文字列長必要になる． たとえば通常のクイックソートで文字列長mのn個の文字列をソートすると \(O(mnlogn)\) となる．

マルチキークイックソートでは文字列の比較を先頭から一文字ずつ行っていく． ピボットとなる文字と比べて辞書順で小さいグループ，同じグループ，大きいグループの3つに分け， 同じグループでは次の位置の文字から，小さい・大きいグループでは同じ位置の文字からそれぞれ再帰的にソートを行う．

参考文献

• 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<http://www.cs.princeton.edu/~rs/strings/>