insertion_sort.hs

module Main where

-- http://files.farka.eu/pub/AC21007/lec5.pdf

insSortImpl :: [Int] -> [Int] -> [Int]
insSortImpl sorted [] = sorted
insSortImpl sorted (x:xs) = 
    insSortImpl (insert x sorted) xs
  where
    insert y [] = [y]
    insert y (z:zs) = if y < z 
      then y : (z:zs) 
      else z : (insert y zs)


insSort :: [Int] -> [Int]
insSort x = insSortImpl [] x


main = print(insSort [8,7,1,6])