main = do cs <- getContents
          putStr $ Insertion_Sort cs

Insertion_Sort :: (a -> a -> Bool) -> [a] -> [a]
Insertion_Sort pred [] = []
Insertion_Sort pred (x:xs) = insert pred x (Insertion_sort pred xs)

insert :: (a -> a -> Bool) -> a -> [a] -> [a]
insert pred x [] = [x]
insert pred x (y:ys)
 | pred x y = (x:y:ys)
 | otherwise = y:(insert pred x ys)