Merge Sort (idea)

Merge sort differs from the other two major O(n log n) algorithms in that it does not require random access to the sequence being sorted.
Merge sort is thus commonly used for sorting linked lists, as well as on-disk structures too large to fit in core. Additionally, merge sort does not require destructive modification, so it can be easily implemented in pure functional languages. For example, in haskell:

merge :: Ord a => [a] -> [a] -> [a]
merge l [] = l
merge [] l = l
merge l@(x:xs) m@(y:ys) =
  if x <= y then x : (merge xs m)
            else y : (merge l ys)

infixl 0 `merge`

oddevn :: [a] -> ([a],[a])
oddevn   []         = ([],[])
oddevn   [x]        = ([x],[])
oddevn   (x:xs)     = let pr = oddevn xs
                      in  (x:snd pr, fst pr)

mergesort :: Ord a => [a] -> [a]
mergesort []  = []
mergesort [x] = [x]
mergesort l   = let pr = oddevn l
                in mergesort (fst pr) `merge` mergesort (snd pr)