insertionSort p [] = []
insertionSort p (x:xs) = fst $ foldl (\(os,m) n -> if not (p m n) then ((insert p os n), m) else (os++[n], n)) ([x], x) xs
    
insert p os u = ls ++ (u:hs)
    where
        (ls, hs) = span (\x -> p x u) os

main = print $ insertionSort (>) [3,4,5,3,2,1,4]

[5,4,4,3,3,2,1]