順序が決まっているものを並べかえる作業は、どう行っているのだろうか。 例えば左から順に 1 からはじめて、最後は King (13) が来るようにしよう。 トランプで 1 つの絵柄 1 組を用意しよう。よく切ったあと、一枚を取り出す。 その一枚よりカードが大きかったら右、小さかったら左、と並べることになる。 4 を取り出した場合
4
次が 9 だったら
49
次が 2 だったら
24
となるだろう。その次のカードも、順次、 始めに引いた数より大きいか小さいかで山を 2 つ作る。 この作業の終了時には
34Q
のように、両側に積み上がっているものである。
完成に近づけるため、とりあえず左側の方を取って、また一枚を置く。今の場合は 1 から 3 である。2 を取った場合を考える。 今と同じ操作を行う。
もし 1 を引いたら、
124Q
とする。3 を引いた場合には 2 の右側にカードを置く。 右側の山も同様にして、全て順番通り並べ終ることを確かめよう。
並べかえが完成すると、全ての数字が並ぶ。
1234 ... K
このような並べかえを quicksort と呼ぶ。