Merge sort (in Haskell)

-- Merge sort
-- Date: Tuesday, March 24, 2009

-- sort a list using merge sort
mergesort [s] =
	[s]
mergesort a =
	let
		mid = ceiling ((fromIntegral (length a))/2)
		(f,s) = splitAt mid a
	in
		merge (mergesort f) (mergesort s)

-- merge two lists
merge :: (Ord t) => [t] -> [t] -> [t]
merge a@(ah:at) b@(bh:bt)
	| ah < bh =
		[ah] ++ merge at b
	| otherwise =
		[bh] ++ merge a bt
-- base case 1: second list empty so we just add everything in a to the end
-- Note: Case [] [] is handled here as well
merge a [] =
	a
-- base case 2: same as above except it is for first list empty
merge [] b =
	b