val it : α → α = fun

前から思っていたんだけど、 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 = length lst
    in
    mergesort len lst
        where mergesort :: (Ord a) => Int -> [a] -> [a]
              merge :: (Ord a) => [a] -> [a] -> [a]
              mergesort 0 lst = []
              mergesort 1 lst = [head lst]
              mergesort n lst =
                  let n1 = n `div` 2
                      n2 = n - n1
                      l1 = lst
                      l2 = drop n1 lst
                  in merge (mergesort n1 l1) (mergesort n2 l2)
              merge [] l2 = l2
              merge l1 [] = l1
              merge l1@(x:xs) l2@(y:ys) =
                  if x < y then x : merge xs l2
                  else y : merge l1 ys

といったところですか。むむむ。思ったより長いなぁ。しかも、上のように書いた割には drop してるところがちょっとダサい気がする。やっぱ qsort は記述の簡潔さがウリなのですね。

調べてみたら hugs/ghc の List.hs の sort はやっぱりマージソートですね。ちょっと長いですが、上に書いたのと方針は逆で、いったんリストの個々の要素を「それ自身のみを含むリスト」とみなし、どんどんマージしていってるみたいですね。そっちの方が速いかなぁ。

ちなみに、 OCaml のソート(List.sort、List.fast_sort、List.stable_sort と3つも関数があるワリに実体はどれも同じ)はマージソートでした。こっちもやたら長いので省略しますが、方針は上に僕が書いたのと同じ。ただ、上手くリストが途中で2回反転するようにして、末尾呼出しにしています。