挿入ソート（Insertion Sort）は、配列を「整列済みの部分」と「未整列の部分」の2つに分け、未整列の部分から要素を1つずつ取り出して、整列済みの部分の適切な位置に割り込ませて（挿入して）いくソートアルゴリズムです。初期状態では、先頭の1要素（インデックス0）だけを「整列済み」とみなし、残りを「未整列」とします。次に、インデックス1の要素を取り出し、整列済みのカード（インデックス0）と比較して、左側に置くべきか右側に置くべきかを判定して挿入します。これを繰り返して、整列済みの壁を右へスライドさせていきます。挿入する際には、挿入先より右側にある整列済みデータをすべて1つずつ右にシフトして空きスペースを作る必要があります。平均および最悪の時間計算量は O(N^2) ですが、このアルゴリズムの特筆すべき長所は、「データが最初からある程度整列されている場合」に劇的に高速に動作する点にあります。完全に整列済みのデータを入力した場合、データのシフトが発生しないため、比較回数は N-1 回で済み、計算量は O(N) となります。また、安定ソートであり、メモリを追記で消費しない（インプレース）ため、シンプルながら実用性の高いアルゴリズムです。