Haskell入門(挿入ソート)

参考ページ
お気楽 Haskell プログラミング入門

挿入ソート
並べ替えられているリストに、
並べ替えられていない要素を適切な位置に挿入する操作を繰り返す。

例
[2, 1, 4, 3]をソートする
右から畳み込む
[]
[3]
[3, 4]
[1, 3, 4]
[1, 2, 3, 4]

insert_element :: Ord a => (a, [a]) -> [a]
insert_element (x, []) = [x]
insert_element (x, xs@(y:ys))
  | x <= y = x:xs
  | otherwise = y : insert_element (x, ys)

insert_sort :: Ord a => [a] -> [a]
insert_sort [] = []
insert_sort (x:xs) = insert_element (x, insert_sort xs)