クイックソート
単語をアルファベット順に並べるとする
A-Mまでで始まるもの・N-Zまでで始まるものの、二つのかたまりに分ける
それぞれをA-F・G-M、N-S・G-Zに分ける
これをかたまりを構成する要素が一つになるまで繰り返す
計算量は$ N\log N
半分にする作業(一つになるまで行う)($ =\log N)を
データの個数($ =N)回行う
データを半分に分けるような、中間の値を知っている(または予測する)必要がある
対象データをおおよそ半分に分けられる場合にのみ優れている