「安定な」クイックソート

id:sawat:20061123の記述に関して。
クイックソートとマージソートの話で、クイックソートは安定でないということが書かれているが、そういう風に書くとさすがに嘘じゃないか？と思ったので。安定と言うのはこの場合、リスト中に同じ大きさの要素があった場合に、その順序が入れ替わらないことを言う。
クイックソートで第一に重要になるのはピボット選択(つまり、比較対象の選択)だが、これをもし仮にリスト(or配列)の中から取ってくるとすると、その値をどこに入れるのか。その作業で不安定になることがある。しかし、クイックソートはリストの対象を二つに分割するわけだが、その操作においては安定であるようにすることが可能である。例えばHaskellなどでよく使われるクイックソートは、

quicksort :: Ord a => [a] -> [a]
quicksort      = 
quicksort (x:xs) =  quicksort [ y | y <- xs, y < x ]
                 ++ [x]
                 ++ quicksort [ y | y <- xs, y >= x ]

のように短くかかれるわけだが(参照：http://oss.timedia.co.jp/show/column/%BA%A3%C6%FC%A4%CE%B0%EC%B9%D4/%A3%B2%A3%B0%A3%B0%A3%B5%C7%AF%A3%B5%B7%EE)、このクイックソートは安定である。ただし、このようなことをする場合には内部的にmallocが必要となる(リストだし・・・)。
わざわざmallocをすると、要素数によっては劇的に遅くなるだろうし、結論としては変わらないけれど、quick sort = 不安定の図式はちょっと気になったので。

あ、前と後ろから順に探索して入れ替えていくタイプのクイックソート(Cなどでよく使われるコード)はもちろん不安定です。ちなみに前後から同時に探索すると言うのは、信じられないくらいの量の要素を入れると、キャッシュの効果がどうのこうので遅くなる、ということも予想されますが、それはまあ気にしない方向で。
後、クイックソートの高速化として、ある程度少ない個数の場合には別のソートを使うというのがありますが、安定が欲しい場合はここでも安定させる必要がどうのこうの。考え出すとめんどくさい。