例えば、１０個の数があって、それらを大きさの順に並べ替える（この操作を、ソート（sort)
という）ことを考える。この問題に対して、多くの人は次のように考えるだろう。
１つの数Ａを選んで、残りの数Ｂと大小を比較する。Ａ≦Ｂなら、Ａはそのまま、Ａ＞Ｂなら、
Ｂを新たにＡとする。この手順を繰り返して最小値を求める。次に、この最小値を除いた残り
について、同じ操作を行い、順次第２最小値、第３最小値、・・・を決めていく。
しかし、この方法だと、最大４４回の大小比較が必要である。
このことについて、次のようなクイックソート（quick sort)という方法が知られている。
ｎ個の異なった数 Ｘ１、Ｘ２、Ｘ３、・・・、Ｘｎ について、
（１） ｎ＝２ のとき、２つの数の大小を比較する。
（２） ｎ＞２ のとき、まず、ｎ個のうちどれか一つＡを任意に選択する。
残りのｎ−１個を、Ａと比較して、ｎ−１個の数を
Ｓ：Ａより小さい数からなる集合
Ｌ：Ａより大きい数からなる集合
という２つの集合に分類する。
この、ＳとＬについて、上記（１）（２）の操作を行い、以下順次繰り返す。
例 １０、３、７、６、１３、１、９、４、８、１１ について、クイックソートを行ってみよう。
１０、３、７、６、１３、１、９、４、８、１１
適当な数、例えば、９を選んで、２つの集合に分類する。
３、７、６、１、４、８ ９ １０、１３、１１ （大小比較の回数 ９回）
適当な数、例えば、６を選んで、２つの集合に分類する。
３、１、４ ６ ７、８ ９ １０、１３、１１ （大小比較の回数 ５回）
適当な数、例えば、３を選んで、２つの集合に分類する。
１ ３ ４ ６ ７、８ ９ １０、１３、１１ （大小比較の回数 ２回）
適当な数、例えば、７を選んで、２つの集合に分類する。
１ ３ ４ ６ ７ ８ ９ １０、１３、１１ （大小比較の回数 １回）
適当な数、例えば、１１を選んで、２つの集合に分類する。
１ ３ ４ ６ ７ ８ ９ １０ １１ １３ （大小比較の回数 ２回）
以上で並べ替えは終了である。この場合の大小比較の回数は全部で１９回である。
もちろん、Ａの選び方によって大小比較の回数は変化するが、並べ替えの方法としては、
だいぶ改善されている筈である。
（参考文献：玉置光司 著 基本確率（牧野書店））