挿入ソート

挿入ソートは新しく追加する要素を適切な位置に挿入していくことで整列させていくアルゴリズム. 単純なため実装も容易となっている。 ほとんど並べられているデータに対しては高速だが、一般的なランダムなデータ等では遅い。 平均計算時間も最悪計算時間もO(n2)$O\left(n^2\right)$となっている

計算のオーバーヘッドが少ないため、 小さいデータ列では他よりも高速なソートとなる。 また、他の上位の再帰を基本とするソートにおいて、小さくなったデータ列で使われることも多い。