merge sort

mergesort.hs

import Data.List
import Test.QuickCheck

mergeSort :: (Ord a) => [a] -> [a]
mergeSort []    = []
mergeSort [x]   = [x] 
mergeSort items = merge l' r'
  where
    (l, r) = halve items 
    l' = mergeSort l
    r' = mergeSort r
    merge xs [] = xs
    merge [] ys = ys
    merge x@(x0:xs) y@(y0:ys)
        | x0 <= y0  = x0 : merge xs y
        | otherwise = y0 : merge x ys
    halve xs = splitAt (length xs `div` 2) xs

prop_mergeSort :: [Int] -> Bool
prop_mergeSort xs = mergeSort xs == sort xs