ソートとマージについて （３）挿入ソート
３．挿入ソート
ソート済データ列の中に、新しいデータを適切な位置に挿入することによって全体を並べ替えるソート方法です。
3.1 ソートされていく様子
サンプルデータが昇順にソートされていく様子です。
０回目
１件目の 44 はソート済とします。
１回目
２件目13は44より小なので44の前に挿入します。
２回目
３件目21は44の前に挿入します。続いて13と比較し、13は移動されてきた21より小なので終了です。
３回目
４件目51はこの位置で適切なので終了です。
４回目
５件目の8は51の前に、更に44の前に、21の前に、13の前で先頭に到達して終了です。
3.2 フローチャート
フローチャートは下図のようになります。
挿入ソートは、元のデータが整列済であるほど処理は早く終わります。
後からデータが追加された場合などには、選択ソートやバブルソートより適しています。
次回は、ソート済データを統合するマージ（Merge）のロジックをご紹介します。
