insertSort :: Ord a => [a] -> [a] insertSort = foldr insert' [] where insert' :: Ord a => a -> [a] -> [a] insert' x [] = [x] insert' x (y:ys) | x <= y = x : y : ys | otherwise = y : insert' x ys

import Data.List (insert) insertSort :: Ord a => [a] -> [a] insertSort = foldr insert []