Haskell MergeSort

mergesort.hs

module Main where

mergeSort :: (Ord a) => [a] -> [a]
mergeSort ns
  -- Recursively call merge s
  | length ns > 1 = merge (mergeSort left, mergeSort right)
  -- This is the base case where recursion stops
  | otherwise = ns
  where
    -- Split the list in half
    (left, right) = splitAt (length ns `quot` 2) ns
    -- Define how to merge two lists
    merge (xs, []) = xs
    merge ([], ys) = ys
    -- Any nonzero length set of lists can be combined recursively
    merge (x:xs, y:ys) = if x < y then x : merge (xs, y:ys) else y : merge (x:xs, ys)

main :: IO()
main = do
  let ns = [10, 9, 8, 7, 2, 4, 5, 2, 32, 6, 5, 4, 3, 2, 1]
  let sortedNs = mergeSort ns
  print sortedNs