Solution: Add a clause

        sort [] = []
        sort [x] = [x]
        sort ls = merge (sort p) (sort q)
          where (p, q) = split ls

The type is now:

        sort :: (Ord a) => [a] -> [a]