Haskell implementation of MergeSort

Merge sort explanation http://en.wikipedia.org/wiki/Merge_sort

mergeSort xs = merge (split xs) []
where split [] = []
split (x:xs) = [x]:split xs

merge [] [] = []
merge (x:x1:xs) ys = merge xs ((sort x x1):ys)
merge [x] ys = merge (x:ys) []
merge [] [y] = y
merge [] ys = merge ys []

sort (x:xs) (y:ys) | x<y = x:(sort xs (y:ys))
|otherwise = y:(sort (x:xs) ys)

sort [] ys = ys
sort xs [] = xs

–sample run
mergeSort [1,50,31,89,0,30,45,67,67,51]
[0,1,30,31,45,50,51,67,67,89]

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s