insertion sort

insertionsort.hs

import Data.List
import Test.QuickCheck

insertionSort :: Ord a => [a] -> [a]
insertionSort = foldr isort []
  where
    isort x [] = [x]
    isort x (y:ys)
        | x > y     = y : isort x ys
        | otherwise = x : y : ys

prop_insertionSort :: [Int] -> Bool
prop_insertionSort xs = insertionSort xs == sort xs