挿入ソート（Insertion Sort）は、配列を「整列済みの部分」と「未整列の部分」の2つに分け、未整列の部分から要素を1つずつ取り出して、整列済みの部分の適切な位置に割り込ませて（挿入して）いくソートアルゴリズムです。初期状態では、先頭の1要素（インデックス0）だけを「整列済み」とみなし、残りを「未整列」とします。次に、インデックス1の要素を取り出し、整列済みのカード（インデックス0）と比較して、左側に置くべきか右側に置くべきかを判定して挿入します。これを繰り返して、整列済みの壁を右へスライドさせていきます。挿入する際には、挿入先より右側にある整列済みデータをすべて1つずつ右にシフトして空きスペースを作る必要があります。平均および最悪の時間計算量は O(N^2) ですが、このアルゴリズムの特筆すべき長所は、「データが最初からある程度整列されている場合」に劇的に高速に動作する点にあります。完全に整列済みのデータを入力した場合、データのシフトが発生しないため、比較回数は N-1 回で済み、計算量は O(N) となります。また、安定ソートであり、メモリを追記で消費しない（インプレース）ため、シンプルながら実用性の高いアルゴリズムです。
試験では、挿入ソートの「すでに整列に近い状態であるデータに対して非常に高速に動作する（最良の計算量は O(N) になる）」という最大の特徴が非常によく出題されます。アルゴリズムのトレース問題では、取り出した値を左側の整列済みデータと順番に比較し、適切な位置を見つけて割り込ませる過程での「データの右シフト（代入処理）」がどのように行われているかをソースコードから読み取る能力が求められます。
インプレース（追加のメモリをほとんど使わず、元の配列内で処理を完結させる方式）、シフト（配列の要素を隣のインデックスへ移動させる処理）、シェルソート（挿入ソートを改良した高速な整列アルゴリズム）。