Daily Archives: July 19th, 2004

前から思っていたんだけど、 Haskell でいうと次に相当するクイックソート。
qsort :: (Ord a) => [a] -> [a]
qsort [] = []
qsort (a:ax) = qsort [x | x <- ax, x < a] ++ [a] ++ qsort [x | x <- ax, x >= a]

これって、記述の容易さ、シンプルさ、再帰的処理による分割統治法など、いろいろ見るべきところはあると思うんですが、はっきり言って全然速くないですよね。リスト内包表記
するとシンプルかつ(比較的)効率的なのはマージソートなのかな、という気がします。ただ、リストを半分で割る、というところがちと面倒かな。長さを求めるとなると、やっぱり全体を読まないといけないので効率が良く無さげな。長さを与えておけば良いのかな。とすると、
msort :: (Ord a) => [a] -> [a]
msort lst =
let len [...]