import List (last, scanl)
insert :: a -> [a] -> [a]
insert x ys = x : ys
insert x (y:ys) = y : insert x ys
permute :: [a] -> [a]
permute = foldl (flip insert) []
insertions :: [a] -> [[a]]
insertions = scanl (flip insert) []
isSorted :: [Int] -> Bool
isSorted [] = True
isSorted [_] = True
isSorted (x:y:zs) = x <= y && isSorted (y:zs)
psort :: [Int] -> [Int]
psort xs | isSorted p = p
where
p = permute xs
isort :: [Int] -> [Int]
isort xs | all isSorted ps = last ps
where
ps = insertions xs