gistfile1.hs

--Implements Mergesort

mergeLists :: (Ord a) => [a] -> [a] -> [a] -> [a]
mergeLists acc xa xb 
	| null xa && null xb 		  = reverse acc --We are complete
	| null xa					        = mergeLists ((head xb):acc) [] (tail xb) --Only b left
	| null xb					        = mergeLists ((head xa):acc) (tail xa) [] --Only a left
	| (head xa) <= (head xb)	= mergeLists ((head xa):acc) (tail xa) xb --a first
	| otherwise					      = mergeLists ((head xb):acc) xa (tail xb) --b first

mergeSort :: (Ord a) => [a] -> [a]
mergeSort xs
	| length xs == 1	= xs
	| otherwise			  = let (xa, xb) = splitAt (quot (length xs) 2) xs
							        in mergeLists [] (mergeSort xa) (mergeSort xb)