巨人の肩の上に登る

先人の積み重ねた発見に基づいて、なにかを発見しようとすることを指す。

挿入ソート

単純なソートアルゴリズム.
計算量は O(n2).

  1. 空リストは整列されているものとする
  2. 整列しているリストに対して,1つの要素を正しい場所に挿入する
insert                      :: Ord a => a -> [a] -> [a]
insert x [ ]                = [x]
insert x (y:ys) | x <= y    = x : y : ys
                | otherwise = y : insert x ys


isort   :: Ord a => [a] -> [a]
isort [ ]    = [ ]
isort (x:xs) = insert x (isort xs)