Haskellで遊ぶよ

Merge Sort

05:47

せっかく Insertion Sort をやったので、マージソートもやってみる。

mergeSort :: Ord a => [a] -> [a]
mergeSort = mergeSortBy compare

mergeSortBy :: Ord a => (a -> a -> Ordering) -> [a] -> [a]
mergeSortBy _ [] = []
mergeSortBy _ [x] = [x]
mergeSortBy cmp xs = mergeBy cmp (mergeSortBy cmp ys) (mergeSortBy cmp zs)
    where 
        (ys,zs) = split xs

split :: [a] -> ([a], [a])
split [] = ([],[])
split [x] = ([x],[])
split (x:x':xs) = (x:as, x':bs)
    where (as, bs) = split xs

mergeBy :: Ord a => (a -> a -> Ordering) -> [a] -> [a] -> [a]
mergeBy _ xs [] = xs
mergeBy _ [] ys = ys
mergeBy cmp xs@(x:xs') ys@(y:ys') = 
    if cmp x y == GT 
        then y:(mergeBy cmp xs ys')
        else x:(mergeBy cmp xs' ys)

main = print $ mergeSort [2,3,4,5,4,3,6,3,2]

実行↓

• Haskell code by edvakf - 25 lines - codepad

本来の安定なマージソートなら split で前半と後半に分けないといけないところだけど、Haskell の length 演算子は O(n) なので、何度も呼びたくない。だから「とびとび」に要素を取っている。

だからこれは非安定ソート。

length を最初に一回だけ計算しておく方法だと

mergeSort :: Ord a => [a] -> [a]
mergeSort = mergeSortBy compare

mergeSortBy :: Ord a => (a -> a -> Ordering) -> [a] -> [a]
mergeSortBy cmp xs = mergeSortBy' cmp xs $ length xs

mergeSortBy' :: Ord a => (a -> a -> Ordering) -> [a] -> Int -> [a]
mergeSortBy' _ [] _ = []
mergeSortBy' _ [x] _ = [x]
mergeSortBy' cmp xs len = mergeBy cmp (mergeSortBy' cmp ys a) (mergeSortBy' cmp zs b)
    where
        (a,b) = if even len then (len `div` 2, len `div` 2) else (len `div` 2 + 1, len `div` 2)
        (ys, zs) = splitAt a xs

mergeBy :: Ord a => (a -> a -> Ordering) -> [a] -> [a] -> [a]
mergeBy _ xs [] = xs
mergeBy _ [] ys = ys
mergeBy cmp xs@(x:xs') ys@(y:ys') =
    if cmp x y == GT
    then y:(mergeBy cmp xs ys')
    else x:(mergeBy cmp xs' ys) 

main = print $ mergeSort [2,3,4,5,4,3,6,3,2]

のようになるはず。

実行↓

• Haskell code by edvakf - 23 lines - codepad

↓に載ってる splitrec というやつだと、リストの長さが分からなくても前半と後半に分けられるみたい。

• Merge sort (Haskell) - LiteratePrograms

どれが速いんだろうか。