/prog/ - Haskell mergesort

Name: Anonymous 2012-04-24 5:29

Haskell newbie here, how is my mergesort?



merge :: (Ord a) => [a] -> [a] -> [a]

merge [] ys = ys

merge xs [] = xs

merge (x:xs) (y:ys) = if (x < y) then x:(merge xs (y:ys)) else y:(merge (x:xs) ys)



mergeSort :: (Ord a) => [a] -> [a]

mergeSort []  = []

mergeSort [x] = [x]

mergeSort xs  = let mid   = (length xs) `div` 2

                    parts = (splitAt mid xs)

                    left  = mergeSort (fst parts)

                    right = mergeSort (snd parts)

                in merge left right

Name: Anonymous 2012-04-24 15:57

sort = sortBy compare

sortBy cmp = mergeAll . sequences

  where

    sequences (a:b:xs)

      | a `cmp` b == GT = descending b [a]  xs

      | otherwise       = ascending  b (a:) xs

    sequences xs = [xs]



    descending a as (b:bs)

      | a `cmp` b == GT = descending b (a:as) bs

    descending a as bs  = (a:as): sequences bs



    ascending a as (b:bs)

      | a `cmp` b /= GT = ascending b (\ys -> as (a:ys)) bs

    ascending a as bs   = as [a]: sequences bs



    mergeAll [x] = x

    mergeAll xs  = mergeAll (mergePairs xs)



    mergePairs (a:b:xs) = merge a b: mergePairs xs

    mergePairs xs       = xs



    merge as@(a:as') bs@(b:bs')

      | a `cmp` b == GT = b:merge as  bs'

      | otherwise       = a:merge as' bs

    merge [] bs         = bs

    merge as []         = as

Haskell mergesort

1 Name: Anonymous 2012-04-24 5:29

17 Name: Anonymous 2012-04-24 15:57

Name: Anonymous 2012-04-24 5:29

Name: Anonymous 2012-04-24 15:57