## 2009-12-02

### 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]
```

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

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]
```

のようになるはず。

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

どれが速いんだろうか。