stable quick sort

Algorithm

stable な quick sort もあるよ、という話なのだが。

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

これは遅そうだなぁ。in-place にはできないのか？じゃないとメモリ消費量がすごそう。

ただし、このようなことをする場合には内部的にmallocが必要となる(リストだし・・・)。

連結リストだからといって毎回動的メモリ確保が必要かといえばそうでもない。必要なサイズがあらかじめ分かれば1度大きな配列を作ってインデックスをポインタ代わりに使えば済む。
そもそも、問題は malloc がどうのこうのいうよりはパーティショニングを高速にできるかどうかで、安定にやろうと思うと、これが案外簡単ではないという話では。この例ではリストを2回走査しているし、pivot を先頭要素以外にしちゃうとこれまた面倒だし*1。

ちなみに前後から同時に探索すると言うのは、信じられないくらいの量の要素を入れると、キャッシュの効果がどうのこうので遅くなる、ということも予想されますが、それはまあ気にしない方向で。

前後から同時に走査しようとそれぞれで局所参照性はあるので、たいしたことはないと思う。キャッシュが1ブロックしかないなら別だけど。
で、なんか性能比較した論文ないかなとちょっと探してみたけど、短い時間だといいのが見つからなかった。が、代わりに 2ch のスレッドが見つかった。

*1:途中でpivotを変更しちゃえばいいといえばいいけど